Dijkstra algoritm
Dijkstra algoritm on Edsger Wybe Dijkstra poolt 1959. aastal avaldatud graafi läbimise algoritm, mis leiab sidusas graafis lühimad teed algtipust kõigisse teistesse tippudesse. Seda algoritmi kasutatakse tihti marsruutimisel. Dijkstra algoritm on ahne algoritm. Algoritm leiab graafi etteantud algtipust vähima kaalutud pikkusega ahelad (ehk lühimad teed) algtipu ja kõigi ülejäänud tippude vahel. Seda võib kasutada ka lühima tee leidmiseks kindlast algtipust 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). Dijkstra algoritm töötab sidusas graafis. Kui graaf pole sidus, siis igast tipust igasse tippu teed ei eksisteerigi ja seda ei saa ka leida. Siiski saab mittesidusateski graafides kasutada Dijkstra algoritmi tippudevahelise lühima tee leidmiseks, kui see eksisteerib, samuti kontrollimiseks, kas ühest tipust teise tee üldse olemas on. Dijkstra algoritmi saab rakendada mittenegatiivsete kaaludega graafis lühimate teede leidmiseks. Kui graafis on negatiivsed kaalud, siis tuleks kasutada kas Bellmanni-Fordi või Floydi-Warshalli algoritmi. Mikkel Thorupi hinnangul on kõik hilisemad ainsa allikaga lühima tee ülesande (single-source shortest-path problem) teoreetilised uurimused tuginenud Dijkstra algoritmile.