En Kısa Yol Algoritmaları
En kısa yol algoritmaları, ağırlıklı bir grafikteki düğümler (vertices) arasında minimum ağırlıklı rotaları hesaplar; farklı algoritmalar negatif olmayan ağırlıklara, negatif ağırlıklara ve tüm çiftler (all-pairs) ile tek kaynaklı (single-source) sorgulara uygun olarak kullanılmaktadır.
Tanım
Ağırlıklı bir grafikte iki düğüm arasındaki en kısa yol, toplam kenar ağırlığı minimum olan yoldur; en kısa yol algoritmaları, bu tür yolları ve mesafelerini, ya tek bir kaynaktan tüm düğümlere ya da tüm düğüm çiftleri arasında hesaplamaktadır.
Kapsam
Bu konu, tek kaynaklı en kısa yolları (negatif olmayan ağırlıklar için Dijkstra algoritması, negatif ağırlıklı grafikler ve negatif döngüleri tespit etmek için Bellman-Ford algoritması), tüm çiftler en kısa yolları (Floyd-Warshall, Johnson algoritması) ve yönlendirilmiş döngüsel olmayan grafiklerdeki en kısa yolları kapsamaktadır. Bu yöntemlerde ortak olan gevşetme prensibini ve verimli uygulamada öncelik kuyruklarının rolünü ele almaktadır. Grafik geçişi (graph traversal) altında ele alınan genişlik öncelikli arama (breadth-first search) ile elde edilen ağırlıksız en kısa yollar bu kapsamın dışındadır.
Temel sorular
- Kenar gevşetme (edge relaxation), mesafe tahminlerini gerçek en kısa mesafelere doğru aşamalı olarak nasıl sıkılaştırmaktadır?
- Dijkstra algoritması, doğru çalışması için neden negatif olmayan kenar ağırlıkları gerektirmektedir?
- Bellman-Ford algoritması negatif ağırlıkları nasıl işler ve negatif döngüleri nasıl tespit eder?
- Tüm çiftler en kısa yollarını hesaplamak, tek kaynaklı bir yöntemi tekrarlamaktan ne zaman daha verimli olmaktadır?
- Öncelik kuyruğu seçimleri, Dijkstra algoritmasının çalışma süresini nasıl etkilemektedir?
Anahtar kavramlar
- kenar gevşetme
- tek kaynaklı en kısa yollar
- Dijkstra algoritması
- Bellman-Ford algoritması
- negatif ağırlıklı döngüler
- tüm çiftler en kısa yollar
- Floyd-Warshall algoritması
- öncelik kuyruğu uygulaması
Temel kuramlar
- Kenar gevşetme ve açgözlü seçim
- En kısa yol algoritmaları, daha kısa bir rota bulunduğunda bir mesafe tahminini değiştirerek kenarları tekrar tekrar gevşetir; Dijkstra algoritması, en yakın yerleşmemiş düğümü açgözlü bir şekilde kesinleştirir ve bu durum, kenar ağırlıklarının negatif olmamasından dolayı doğru kabul edilmektedir.
- Tüm çiftler yolları için dinamik programlama
- Floyd-Warshall algoritması, ara düğümler üzerinde dinamik bir program aracılığıyla tüm çiftler en kısa yollarını hesaplar; kübik zamanda çalışır ve negatif kenar ağırlıklarını (negatif döngüler olmadan) doğal olarak işleyebilmektedir.
Klinik önem
En kısa yol algoritmaları, navigasyon ve haritalama hizmetleri, ağlardaki paket yönlendirme protokolleri, lojistikte rota planlaması ve oyunlarda yol bulma (pathfinding) ile uzamsal analizde kaynak-mesafe hesaplamaları dahil olmak üzere, ağırlıklı bir ağ üzerinden en düşük maliyetli yolları bulan her türlü sisteme güç vermektedir.
Tarihçe
Dijkstra, tek kaynaklı en kısa yol algoritmasını 1959'da yayımlamıştır. Negatif ağırlıkları işleyen Bellman-Ford algoritması, 1950'lerin sonlarında Bellman, Ford ve Moore'un çalışmalarından ortaya çıkmıştır. Warshall'ın geçişli kapanım (transitive-closure) yöntemine dayanan Floyd'un 1962 algoritması, günümüzde hala bir standart olarak kabul edilen kompakt bir tüm çiftler çözümü sunmuştur.
Öne çıkan isimler
- Edsger W. Dijkstra
- Richard Bellman
- Lester Ford
- Robert W. Floyd
İlgili konular
Temel eserler
- dijkstra1959
- floyd1962
- cormen2009
Sıkça sorulan sorular
- Dijkstra algoritması neden negatif kenar ağırlıklarını işleyemez?
- Dijkstra algoritması, en yakın yerleşmemiş düğümü kesinleştirir ve daha sonra hiçbir yolun daha kısa olamayacağını varsayarak onu asla yeniden ziyaret etmez. Negatif bir kenar, bir düğüm yerleştikten sonra böyle daha kısa bir yol oluşturabilir ve bu varsayımı bozabilir. Bunun yerine, tüm kenarları tekrar tekrar gevşeten Bellman-Ford algoritması kullanılmaktadır.
- Her düğümden Dijkstra algoritmasını çalıştırmak yerine tüm çiftler algoritmasını ne zaman kullanmalıyım?
- Yoğun grafikler için veya birçok ya da tüm kaynak-hedef mesafeleri gerektiğinde, Floyd-Warshall'ın basit kübik zamanlı tüm çiftler hesaplaması genellikle tercih edilmektedir. Seyrek grafikler için, her kaynaktan Dijkstra (veya negatif ağırlıklar için Johnson algoritması) çalıştırmak asimptotik olarak daha hızlı olabilmektedir.