Algoritmalar[değiştir | kaynağı değiştir]
Bu problemi çözen en bilindik algoritmalar şunlardır:
- Dijkstra algoritması: ayrıt ağırlıkları eksi değerli olmamak üzere, tek kaynaklı en kısa yol problemini çözer.[1]
- Bellman–Ford algoritması: eksi değerli ayrıt ağırlıklarına izin verir şekilde, tek kaynaklı en kısa yol problemini çözer.
- A* arama algoritması: iki düğüm arasındaki en kısa yolu bulur ve sezgisel yöntemlerle aramayı hızlandırır.
- Floyd-Warshall algoritması: bütün düğüm çiftleri için en kısa yolları bulur, eksi değere izin verir.
- Johnson algoritması: bütün düğüm çiftleri için en kısa yolları bulur, seyrek çizgelerde Floyd–Warshall algoritmasından daha hızlı çalışabilir.
- Viterbi algoritması: ayrıtların olasılıksal ağırlıkları olan stokastik en kısa yol problemini çözer.
Özel durumlarda kullanışlı olan birçok algoritma mevcuttur.