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.

Ağırlıklı yönlü bir çizgede, A ve F düğümlerini birleştiren en kısa yol (A, C, E, D, F).

Algoritmalar

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

1. Uyar, Barış. "En Kısa Yol Problemi ve Dijkstra Algoritması". Bilişim IO. 22 Temmuz 2017 tarihinde kaynağından arşivlendi.