Dijkstra algoritması

Rota planlayıcınız kapınızdan neredeyse her yere giden en hızlı yolu bilir. Bu fikrin özünde, Edsger Dijkstra'nın 1956'da yaklaşık yirmi dakikada bulduğu bir algoritma vardır: başlangıçtan dışarı doğru büyü ve her zaman önce en yakın yeri bitir.

Kenarlarının uzunlukları olan bir graf; başlangıca yakın düğümler yeşil renkte bitmiş, en kısa rotalardan oluşan bir ağaç ve altında çizilmiş bir öncelik kuyruğu
Kenarlarının uzunlukları olan bir graf; başlangıca yakın düğümler yeşil renkte bitmiş, en kısa rotalardan oluşan bir ağaç ve altında çizilmiş bir öncelik kuyruğu

Fikir

Farklı uzunlukta yollarla birbirine bağlı şehirler düşünün. Soru şu: benim şehrimden diğer her şehre en kısa yol hangisi? Her yol aynı sayıldığında genişlik öncelikli arama bunu yanıtlar, ama burada daha çok yoldan oluşan bir rota daha kısa olabilir. Dijkstra algoritması her şehir için şimdiye kadar bulunan en kısa uzaklığı tutar ve uzaklığı kesin olan şehirlerden oluşan bir bölgeyi büyütür; her seferinde uzaklığı henüz kesin olmayan en yakın şehri ekler.

Adım adım

Başlangıca uzaklık 0, diğer her düğüme sonsuz verin. Başlangıcı bir öncelik kuyruğuna, yani her zaman en küçük uzaklığa sahip düğümü veren bir kuyruğa koyun. O düğümü alın; uzaklığı artık kesindir. Kesinleşmemiş her komşu için bu düğüm üzerinden uzaklığı hesaplayın: düğümün uzaklığı artı kenarın uzunluğu. Bu, komşunun şimdiye kadarki uzaklığından küçükse uzaklığı düşürün, bu düğümü oraya giden yol olarak hatırlayın ve komşuyu kuyruğa koyun. Buna bir kenarı gevşetmek denir. Kuyruk boşalana ya da hedef kuyruktan alınana kadar tekrarlayın.

Bir örnek

Kenarlar şöyle olsun: A–B uzunluk 4, A–C 1, B–C 2, B–D 1, C–D 5 ve D–E 3; A'dan başlayın. A alınınca B'nin uzaklığı 4, C'nin uzaklığı 1 olur. En yakın C'dir, yani 1 ile kesinleşir; C üzerinden B 1 + 2 = 3'e düşer ve D 1 + 5 = 6 alır. Şimdi en yakın B'dir, 3 ile kesinleşir ve B üzerinden D 3 + 1 = 4'e düşer. D 4 ile kesinleşir ve E'ye 4 + 3 = 7 verir. Yani A'dan E'ye en kısa yol, uzunluğu 7 olan A → C → B → D → E'dir; oysa A → B → D → E daha az kenar kullanır ve uzunluğu 8'dir.

Neden doğrudur

X düğümünün kuyruktaki en yakın düğüm olduğunu ve uzaklığının d olduğunu varsayalım. Başlangıçtan X'e giden başka her yol bir noktada kesin düğümler bölgesinden çıkmak zorundadır ve bu bölgenin dışında ulaştığı ilk düğüm kuyruktadır; yani zaten en az d uzaktadır. Yolun geri kalanı onu kısaltamaz, çünkü hiçbir kenar negatif değildir. Yani d, X'e olan en kısa uzaklıktır. Negatif bir kenar varsa bu akıl yürütme çöker; bunun yerine her kenarı tekrar tekrar gevşeten Bellman–Ford algoritması kullanılır.

Tarihçe ve kullanım alanları

Edsger W. Dijkstra algoritmayı 1956'da, Amsterdam'daki yeni bir bilgisayar olan ARMAC'ı tanıtmak için Hollanda şehirleri arasında rotalar bularak tasarladı ve 1959'da yayımladı. Aynı fikir, daha akıllı bir kuyrukla, rota planlayıcılarında ve verinin yönlendiriciler arasında izleyeceği en kısa yolu hesaplayan OSPF ve IS-IS gibi internet yönlendirme protokollerinde çalışır. A* araması kalan uzaklık için bir tahmin ekler; böylece hedefe yönelebilir ve daha az düğüme bakar.

Edsger W. Dijkstra kara tahtanın başında
Edsger W. Dijkstra kara tahtanın başında

Keşfedin

Uygulamayı açın ve Adım'a basın. Kenarlardaki sayılar kenarların uzunluklarıdır, her düğümdeki sayı da o düğümün şimdiye kadarki uzaklığıdır. Kuyruktaki düğümler mavi, kesinleşen düğümler yeşildir; grafın altındaki kuyruk onları uzaklıklarıyla birlikte, en yakını başta olmak üzere listeler. Daha uzun görünen bir rota daha kısa çıktığı için bir uzaklığın düştüğü anlara dikkat edin ve hedef kesinleşir kesinleşmez aramanın durduğunu görmek için bir hedef seçin.

Sık sorulan sorular

Dijkstra algoritmasının zaman karmaşıklığı nedir?

Öncelik kuyruğuna bağlıdır. Basit bir listeyle V düğüm için O(V²); ikili yığınla E kenar için O((V + E) log V); Fibonacci yığınıyla, Michael Fredman ve Robert Tarjan'ın 1984'te gösterdiği gibi, O(E + V log V).

Dijkstra algoritması negatif kenar ağırlıklarıyla çalışabilir mi?

Hayır. Bir düğüm kuyruktaki en yakın düğüm olduktan sonra uzaklığının iyileşemeyeceğini varsayar; negatif bir kenar bunu bozabilir. Negatif kenarlı graflar için Bellman–Ford algoritmasını kullanın.

Dijkstra algoritması her düğüme giden yolu bulur mu?

Evet. Sonuna kadar çalıştırıldığında başlangıçtan ulaşılabilen her düğüme en kısa uzaklığı verir ve hatırlanan düğümler bir en kısa yollar ağacı oluşturur. Yalnızca bir yol gerektiğinde, hedef kesinleşince erken durmak iş tasarrufu sağlar.

Dijkstra algoritmasının A* ile ilişkisi nedir?

A* araması, ipucu eklenmiş Dijkstra algoritmasıdır: kuyruğu şimdiye kadarki uzaklık artı kalan uzaklığın bir tahminine göre sıralar; örneğin haritadaki kuş uçuşu uzaklık. İyi bir tahminle aynı en kısa yolu çok daha az düğüme bakarak bulur.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Dijkstra algoritmasını deneyin