Shortest Path Problem

Shortest Path Problem (SPP), ağırlıklı bir grafta (yönlendirilmiş ya da yönsüz) iki düğüm arasında minimum toplam kenar ağırlığına sahip yolu bulma problemidir; üç temel varyantı vardır: single-source single-destination (tek nokta-noktaya), single-source all-destinations (tek kaynaktan tüm hedeflere), all-pairs (tüm-çift). Foundational graf-OR problemi; non-negatif kenarlar için kanonik çözüm Dijkstra (1959) tarafından *Numerische Mathematik*'te iki sayfalık makalede tanımlanan polinom-zaman algoritmasıdır (binary heap implementasyonu O((V+E)logV)). Negatif kenarlar için Bellman-Ford (Bellman 1958), O(VE) ile çözer ve negatif cycle algılaması yapar. Tüm-çift için Floyd-Warshall (Floyd 1962) dinamik programlama ile O(V³). Ahuja-Magnanti-Orlin (1993) *Network Flows* kanonik ders kitabıdır. Modern endüstride en sık çağrılan OR algoritması — navigasyon servisleri, harita servisleri, paket-yönlendirme protokolleri (OSPF), kargo dağıtım sıralama, otoyol rota planlama altında çalışır; ülke ölçeği yol ağları için modern preprocessing-tabanlı yaklaşımlar (contraction hierarchies — Geisberger 2008) milisaniye-altı sorgu süresi sağlar. TSP (#068) ve VRP (#002) shortest path'i alt-rutin olarak çağırır, ama farklı problemlerdir: shortest path polinom-zaman, TSP/VRP NP-hard.