Dijkstra algoritm
Dijkstra algoritm on Hollandi informaatiku Edsger Dijkstra poolt 1959. aastal avaldatud[1] graafi läbimise algoritm, mis leiab lühima tee kahe suvalise graafi tipu vahel. Seda algoritmi kasutatakse tihti marsruutimisel.
Algoritm leiab graafi etteantud lähtetipust vähima kaalutud pikkusega ahelad (ehk lühimad teed) lähtetipu ning kõigi teiste tippude vahel. Seda võib kasutada ka lühima tee leidmiseks kindlast lähtetipust kindlasse lõpptippu, peatades algoritmi, kui lühim tee lõpptippu on leitud. Näiteks, kui graafi tipud tähistavad linnu ja servade kaalud tähistavad kahe omavahel teega ühendatud linna vahelist vahemaad, siis saab Dijkstra algoritmi kasutades leida lühimad teekonnad reisi lähtelinnast kõigisse teistesse linnadesse. Lühima tee leidmise algoritmi kasutatakse laialdaselt võrgu marsruutimisprotokollides, tuntumaid neist on IS-IS ja OSPF (Open Shortest Path First).
Vaata ka
Viited
- ↑ Edsger W. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik, nr. 1, 1959, lk 269–271