Dijkstra lühim tee

Dijkstra algoritm leiab lühima tee sõlmede vahel mitte-negatiivsete kaaludega graafis. See töötab ahnelt (greedy), uuendades kaugusehinnanguid relaksatsiooni kaudu: d(v) = min(d(v), d(u) + w(u,v)). Ajaline keerukus on optimeeritud tasemele O(E + V log V), kasutades Fibonacci kuhja prioriteedijärjekorda.

Dijkstra kasvatab alguspunktist väljapoole rinnet ja valib alati lähima veel külastamata tipu. Kuna kõik kaalud on mittenegatiivsed, ei suuda ükski hilisem ümbertee võita juba leitud lühemat teed — kui tipp on kord kinnitatud, on selle kaugus lõplik ja seda ei vaadata enam üle. Seetõttu toetuvad marsruudiplaneerijad ja võrguprotokollid nagu OSPF sellele usaldusväärsete lühimate teede arvutamiseks.

Edsger Dijkstra mõtles algoritmi 1956. aastal välja umbes kahekümne minutiga, ilma pliiatsi ja paberita, puhates Amsterdami kohviku terrassil. Ta otsis näiteülesannet arvutile ARMAC ja valis lühima marsruudi kahe Hollandi linna, Rotterdami ja Groningeni vahel. Kolm aastat hiljem avaldas ta selle vaevalt kolmeleheküljelises artiklis — ühes informaatika enim tsiteeritud tulemuses.