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.
• 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.