Dijkstra
Kenar ağırlıkları negatif olmayan bir çizgede kaynaktan diğer tüm düğümlere en kısa yolu bulan klasik algoritma; Edsger Dijkstra (1956, yayını 1959).
Fikir şu: bilinen en düşük mesafeli düğümü keşfet, komşuları güncelle, tekrarla. Öncelik kuyruğu olarak ikili yığınla karmaşıklık O((V+E) log V); Fibonacci yığınıyla O(E + V log V) olur. Kâğıt üzerinde daha hızlıdır, pratikte nadiren fark yaratır.
Tüm GPS rotalamasının, BGP/OSPF yönlendirmesinin, sosyal çizge gezintilerinin ve Pac-Man hayaletlerinin arkasında çalışır. Rakipleri: A* (sezgisel yöntemle, tek çift için daha hızlı), Bellman-Ford (negatif ağırlıklar), Floyd-Warshall (tüm çiftler).