En kısa yol problemi
Çizge kuramında, en kısa yol problemi, bir çizgedeki iki düğümü bağlayan ve ağırlıkları toplamı en az olan ayrıtlar dizisini bulma problemidir.
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.
Kaynakça
[değiştir | kaynağı değiştir]- ^ Uyar, Barış. "En Kısa Yol Problemi ve Dijkstra Algoritması". Bilişim IO. 22 Temmuz 2017 tarihinde kaynağından arşivlendi.
