Dextra algoritem in njegovo izvajanje

V matematiki in informatiki obstaja posebna smer, imenovana teorija grafov. V okviru tega so različne naloge določene in rešene, na primer o iskanju najkrajše poti med tockami. Eden od najpogostejših metod za reševanje tega problema med matematiki je že dolgo algoritem Dijkstra.

Kaj je matematični graf

Menimo, da je koncept grafikona uvedel v osemnajstem stoletju Leonard Euler. To je bil tisti, ki je izrazil formulacijo in rešitev enega od klasičnih problemov te teorije - o sedmih mostovih Koenigsberga. Za razlago predmeta te teorije najpogosteje uporabljamo takšno analogijo kot gibanje med različnimi mesti. Potem bo graf na ravnini predstavljal celotno shemo poti, pri čemer bodo toce določene točke (na primer mesta) in robovi - pot od ene do druge (analogno cesti med mesti). Dijkstrajev algoritem poleg drugih metod omogoča tudi rešitev tega vprašanja.

Iskanje najkrajše poti

Ena od standardnih nalog teorija grafov je tista, v kateri je treba določiti stroškovno optimalno pot med dvema točkama. Na ravnini se lahko zmanjša na rešitev grafikona, v katerem so točke-mesta povezana z robovi, ki predstavljajo možne ceste. In vsaka cesta ima svojo dolžino, zato je za potovanje skozi to potrebno porabiti določena sredstva. Ta vsota je enaka teži roba na grafu. Potem se lahko problem v praksi oblikuje na naslednji način: kako utreti pot iz enega mesta v drugega, da porabi na cesti najmanj sredstev.

Rešitve

Za rešitev tega problema so izumili nekateri algoritmi, ki so postali splošno znani v znanstvenem svetu. Na primer, algoritem Floyd - Warshell, Ford - Bellman. Algoritem Dijkstra je tudi klasičen način iskanja rešitve. Uporablja se lahko tudi za tehtano (znana teža vsakega roba) in za redko. Če želite najti končno pot, morate narediti nekaj korakov.

Algoritem Dijkstra

Pomen te metode je, da se vse tocke zaobidejo, izhajajoč iz danega, pri čemer je vsak dobil oznako z določeno vrednostjo. Nato bo rezultat vključeval tiste tocke, katerih oznake so minimalne. V prvem koraku je prvotnemu vertexu dodeljena etiketa z vrednostjo 0. Torej se upoštevajo vse naslednje vertices, to je tiste, do katerih se lahko dostopa iz izvorne vertexe. Dodeli so oznake, katerih vrednost je opredeljena kot vsota vira in teže poti. Iz tock v naslednjem koraku je izbran eden, ki ima najmanjšo vrednost oznake, in proučujemo vse tocke, do katerih lahko prehajajo brez uporabe vmesnih tock. Določena je nova vrednost oznake, ki je enaka oznaki izvornega vozlišča in težo poti. Če je nastala vrednost manjša od oznake verige, se oznaka spremeni. V nasprotnem primeru ostane izhodiščna vrednost. V tem primeru je v ločeni matriki, katere dimenzija je enaka številu tock v grafu, ohranjen rezultat optimizacije, po kateri se doloca pot. Za izvajanje takšne metode kot algoritem Dijkstra, Pascal ponuja zelo priročna orodja. Algoritem ima prednost, da ga je enostavno uporabiti kot osnova za program, ki ima majhno velikost. Primeri takih programskih izdelkov so enostavno na voljo na internetu.

Za rešitev problema iskanja optimalne poti lahko uporabimo različna sredstva. Za takšno rešitev, kot je Dijkstrajev algoritem, bo Delphi ustvaril vidno priročno obliko vnosa začetnih podatkov in izhod končnega rezultata.