Dijkstra Algoritması — En Kısa Yol Adım Adım

Dijkstra algoritması, ağırlıklı bir grafikte tek bir başlangıç düğümünden en kısa yolları bulur; bunun için tüm kenar ağırlıklarının negatif olmaması gerekir. Yalnızca tek bir hedefle ilgileniyorsanız, o hedef düğüm kesinleşir kesinleşmez durabilirsiniz.

Temel fikir açgözlüdür: her zaman, henüz kesinleşmemiş düğümler arasından bilinen uzaklığı en küçük olan düğümden devam edilir. Bu yaklaşım yalnızca negatif olmayan ağırlık koşulu altında çalışır.

Dijkstra Algoritması Ne İşe Yarar

Kenarlar üzerinde maliyetler bulunan bir grafikte en ucuz rotayı bulmak istediğinizde Dijkstra algoritmasını kullanın. Bu maliyet; mesafe, seyahat süresi, enerji ya da en aza indirmek istediğiniz başka bir büyüklüğü temsil edebilir.

Yönlü veya yönsüz graflarda çalışır. Temel koşul açıktır: her kenar ağırlığı en az $0$ olmalıdır.

Algoritma Nasıl Çalışır

Her düğüm, başlangıç düğümünden olan geçici bir uzaklık değeri tutar. Başlangıçta, başlangıç düğümünün uzaklığı $0$, diğer tüm düğümlerin uzaklığı ise $\infty$ olur.

Sonra şu döngü tekrarlanır:

1. Kesinleşmemiş düğümler arasından geçici uzaklığı en küçük olanı seçin.

2. O düğüm üzerinden her komşuyu kontrol edin.

3. Yeni rota daha ucuzsa komşunun uzaklığını güncelleyin.

4. Geçerli düğümü kesinleşmiş olarak işaretleyin.

5. adıma gevşetme denir. Bir düğüm kesinleştiğinde işi bitmiştir: grafikte negatif kenar ağırlığı yoksa, en kısa uzaklığı artık kesindir.

Dijkstra Algoritması Adım Adım

İşte tüm prosedürün kısa hali:

1. Bir başlangıç düğümü seçin.
2. Onun uzaklığını $0$, diğer tüm uzaklıkları $\infty$ yapın.
3. Kesinleşmemiş düğümler arasından geçici uzaklığı en küçük olanı seçin.
4. O düğümün giden kenarlarını gevşetin.
5. O düğümü kesinleşmiş olarak işaretleyin.
6. Erişilebilen tüm düğümler kesinleşene kadar tekrarlayın ya da hedef düğümünüz kesinleştiğinde durun.

Her güncellemeye hangi önceki düğümün neden olduğunu da saklarsanız, yalnızca son uzaklığı değil, gerçek yolu da geri elde edebilirsiniz.

Çözümlü En Kısa Yol Örneği

Grafikte şu kenar ağırlıkları olduğunu varsayalım:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

$A$ düğümünden $D$ düğümüne en kısa yolu bulmak istiyoruz.

Başlangıç durumu:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Önce $A$ düğümünü kesinleştirin ve kenarlarını gevşetin:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Şimdi kesinleşmemiş en küçük uzaklık $C$ düğümündedir, bu yüzden sıradaki düğüm $C$ olur.

$C$ üzerinden gidersek:

• $C$ üzerinden $B$'ye giden yolun maliyeti $1+2=3$ olur. Bu, $4$ değerinden daha iyidir; dolayısıyla $\text{dist}(B)=3$ olarak güncellenir.
• $C$ üzerinden $D$'ye giden yolun maliyeti $1+5=6$ olur; bu yüzden $\text{dist}(D)=6$ yapılır.

Şimdi kesinleşmemiş en küçük uzaklık $B$ düğümündedir, bu yüzden $B$ düğümünü kesinleştirin.

$B$ üzerinden $D$'ye giden yolun maliyeti:

$$3+1=4$$

Bu, $6$ değerinden daha iyidir; dolayısıyla $\text{dist}(D)$ değeri $6$'dan $4$'e güncellenir.

Artık kesinleşmemiş en küçük düğüm $D$'dir. Onu kesinleştirin ve durun.

En kısa yol şudur:

$$A \to C \to B \to D$$

toplam maliyet ise:

$$1+2+1=4$$

Bu örnek temel deseni gösterir: İlk bakışta daha kötü görünen bir rota, yani $A \to B$, daha sonra $C$ üzerinden daha iyi hale geldi. Dijkstra algoritması, $B$ henüz kesinleşmemişken buna izin verir. Bir düğüm kesinleştikten sonra uzaklığı artık değişmez.

Negatif Olmayan Ağırlıklar Neden Önemlidir

Diyelim ki şu anda en ucuz kesinleşmemiş düğümün uzaklığı $d$ olsun. Daha sonra bu düğüme bulunan herhangi bir yeni yol, geçici uzaklığı en az $d$ olan başka bir kesinleşmemiş düğümden gelmek ve ardından ağırlığı en az $0$ olan bir kenar eklemek zorundadır.

Bu yüzden o sonradan bulunan rota, $d$ değerinden daha iyi olamaz. Tüm ağırlıklar negatif değilse, en küçük geçici uzaklığı kesinleştirmenin güvenli olmasının nedeni budur.

Eğer negatif bir kenar varsa bu gerekçe bozulur. Şu anda pahalı görünen bir yol daha sonra ucuzlayabilir; bu da bir düğümü çok erken kesinleştirmenin yanlış sonuca yol açabileceği anlamına gelir.

Dijkstra Algoritmasında Yaygın Hatalar

Negatif kenarla kullanmak

Tek bir negatif kenar bile açgözlü mantığı bozabilir. Negatif ağırlıklar mümkünse, farklı bir en kısa yol yöntemi kullanın.

"Görüldü" ile "bitti"yi aynı sanmak

Bir düğümün geçici bir uzaklığı zaten olabilir ama yine de işi bitmemiş olabilir. Yalnızca kesinleşmiş bir düğümün en kısa uzaklığı nihaidir.

Önceki düğüm tablosunu unutmak

Uzaklıklar size maliyeti söyler. Rotanın kendisini de istiyorsanız, her uzaklığı en son hangi düğümün iyileştirdiğini saklayın.

Dijkstra Algoritması Nerelerde Kullanılır

Dijkstra algoritması, bir problemin negatif olmayan maliyetlere sahip bir grafikte hareket etme olarak modellenebildiği durumlarda kullanılır:

• Haritalarda rota planlama
• Ağ yönlendirme
• Ağırlıklı ızgaralarda robot hareketi
• Hareket maliyetlerinin değiştiği oyunlarda yol bulma

Ayrıca, doğruluğu kesin bir koşula bağlı olan açgözlü algoritmalara verilen standart örneklerden biridir.

Benzer Bir Problem Deneyin

Beş düğümlü ve pozitif kenar ağırlıklı bir grafik çizin, sonra bir uzaklık tablosu ile Dijkstra algoritmasını elle uygulayın. İyi bir sonraki adım istiyorsanız, yeni bir grafikte kendi örneğinizi deneyin ve her düğümün tam olarak ne zaman güvenle kesinleştirilebildiğini kontrol edin.