Dijkstras algoritme og gjennomføringen

Det er et eget område kalt grafteori i matematikk og informatikk. Som en del av apparatet og for å løse forskjellige problemer, slik som å finne den korteste vei mellom toppunktene. En vanlig blant matematikere måter å løse dette problemet har lenge vært en Dijkstras algoritme.

Hva er en matematisk graf

Det antas at oppfatningen av grafen ble tatt i bruk i det attende århundre leonardom Eylerom. Det var han som annonserte formulering og løsning av en av de klassiske problemene med denne teorien - de syv broene i Königsberg. For å forklare hensikten med denne teorien ofte bruker denne analogien som bevegelse mellom forskjellige byer. Deretter grafen på flyet vil være et helt rute diagram, hvor topp-punktene bli bestemte elementer (f.eks byer), og kantene - bane fra en node til en annen (analog vei mellom byer). Dijkstra, blant andre metoder, kan gi en løsning på dette problemet.

Finne den korteste veien

En av de vanligste oppgavene i grafteori er en der du må finne den optimale kostnaden vei mellom to punkter. Det er mulig å redusere flyet til avgjørelsen av grafen hvor hjørnene - byer - er sammenhengende ribbe, som er en mulig vei. Hver veien har sin egen lengde, derfor reise på det vil måtte bruke noen penger. Denne mengde er ekvivalent med vekten av kanter i grafen. Så problemet i praksis kan formuleres slik: hvordan å rydde vei fra en by til en annen, for å bli brukt på veien minimum midler.

måter å løse

For å løse dette problemet vi har blitt oppfunnet av noen algoritmer som er blitt viden kjent i den vitenskapelige verden. For eksempel, Floyd algoritme - Uorshella, Ford - Bellman. Den klassiske måten å finne løsninger er også Dijkstras algoritme. Den kan brukes for veid (kjent vekt av hver kant) av grafen, og for å fortynne. For å finne den ultimate måten du må gjøre flere trinn.

Dijkstras algoritme

Poenget med denne metoden ligger i det faktum at alle punktene av kost, som begynner med en gitt, hvor hver kode er tilordnet en viss verdi. Så resultatet vil omfatte punktene hvis etikettene er minimal. På toppen av den første innledende skritt vil være merket med en verdi på 0. Da alle følgende topper er vurdert, det vil si de som kan nås fra kilden. De er merket, hvis verdi blir bestemt som summen av kildekoden og vekten av banene. Fra toppen av det neste trinnet, velg den som har den minste verdien av etiketten, og studerte alle hjørnene i at fra det vi kan gå uten å bruke mellomliggende noder. Angi en ny etikett lik etiketten topper - kildekoden pluss vekten av veien. Hvis verdien er lavere enn toppen etiketten, er etiketten endret. Ellers er det fortsatt den opprinnelige verdien. På samme tid i en separat matrise, hvis dimensjon er lik antallet av hjørner, lagrer resultatet av optimaliseringen, i hvilken og bestemt måte. For å implementere en metode som Dijkstras algoritme, Pascal tilbyr en veldig praktisk måte. Algoritmen har den fordelen at det lett kan være grunnlaget for et program som har en liten størrelse. Eksempler på slike programvareprodukter lett å finne på Internett.

DLE løsninger ulike verktøy du kan bruke oppgave å finne den optimale banen. For løsninger som Dijkstra algoritme, vil Delphi skape praktisk form av visuelle data input og output det endelige resultatet.