Çizge kuramında, en kısa yol problemi, bir çizgedeki iki düğümü bağlayan ve ağırlıkları toplamı en az olan dizisini bulma problemidir.
![image](https://www.wikipedia.tr-tr.nina.az/image/aHR0cHM6Ly93d3cud2lraXBlZGlhLnRyLXRyLm5pbmEuYXovaW1hZ2UvYUhSMGNITTZMeTkxY0d4dllXUXVkMmxyYVcxbFpHbGhMbTl5Wnk5M2FXdHBjR1ZrYVdFdlkyOXRiVzl1Y3k5MGFIVnRZaTh6THpOaUwxTm9iM0owWlhOMFgzQmhkR2hmZDJsMGFGOWthWEpsWTNSZmQyVnBaMmgwY3k1emRtY3ZNalV3Y0hndFUyaHZjblJsYzNSZmNHRjBhRjkzYVhSb1gyUnBjbVZqZEY5M1pXbG5hSFJ6TG5OMlp5NXdibWM9LnBuZw==.png)
Algoritmalar
Bu problemi çözen en bilindik algoritmalar şunlardır:
- : ayrıt ağırlıkları eksi değerli olmamak üzere, tek kaynaklı en kısa yol problemini çözer.
- : 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 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.
- : 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
- ^ Uyar, Barış. . Bilişim IO. 22 Temmuz 2017 tarihinde kaynağından arşivlendi.