Dijkstra Algoritması

Veri Yapıları kursunda çizgeler tanımlanmış, enine ve derine arama kurulmuştu. Enine arama, kenar sayısı cinsinden en kısa yolu buluyordu: her kenarın maliyeti eşit sayılıyordu.

Gerçek problemlerde kenarların maliyeti farklıdır — mesafe, süre, ücret. Bu konu ağırlıklı çizgelerde çalışan algoritmaları kurar ve ilk sorusu en kısa yoldur.

Problem ve Gösterim

Tek kaynaktan en kısa yol problemi: Ağırlıklı bir çizge ve bir kaynak düğüm verilir; kaynaktan diğer tüm düğümlere giden en düşük toplam ağırlıklı yollar istenir.

Bu konu boyunca aynı çizge kullanılır: düğümler A–F, kenarlar yönlü ve ağırlıklı.

cizge: dict[str, list[tuple[str, int]]] = {
    "A": [("B", 4), ("C", 2)],
    "B": [("C", 5), ("D", 10)],
    "C": [("E", 3)],
    "D": [("F", 11)],
    "E": [("D", 4)],
    "F": [],
}

Komşuluk listesi gösterimi, seyrek çizgelerde uygundur ve tüm kenarları gezmek $O(V + E)$’dir. Yoğun çizgelerde komşuluk matrisi tercih edilir; seçimin maliyet üzerindeki etkisi Veri Yapıları kursunda ele alınmıştı.

Gevşetme

Algoritmaların ortak yapı taşı gevşetmedir (relaxation): bilinen bir tahmini, bulunan daha iyi bir yolla düşürmek.

Her düğüm için kaynaktan gelen en iyi bilinen uzaklık u[v] tutulur; başlangıçta kaynak için $0$, diğerleri için sonsuzdur. (v, w) kenarı için:

$$u[w] > u[v] + \text{ağırlık}(v, w) \implies u[w] \leftarrow u[v] + \text{ağırlık}(v, w)$$

Gevşetme hiçbir zaman yanlış bir değer üretmez: u[w] her zaman gerçekten var olan bir yolun uzunluğudur. Algoritmalar, bu değerlerin ne zaman kesinleştiğine dair verdikleri güvenceyle ayrılır.

Açgözlü Seçim

Dijkstra algoritmasının fikri şudur: henüz kesinleşmemiş düğümler arasında en küçük tahmini olan düğüm, artık kesinleşmiştir.

Gerekçe, ağırlıkların negatif olmamasına dayanır. Kaynaktan v’ye giden herhangi bir başka yol, kesinleşmemiş bir düğümden geçmek zorundadır; o düğümün tahmini u[v]’den küçük olmadığına ve kalan kenarlar maliyeti azaltamayacağına göre, alternatif yol daha kısa olamaz.

Bu akıl yürütme, algoritmanın değişmezini verir: kesinleşmiş düğümlerin uzaklıkları gerçek en kısa yol uzunluklarıdır.

Gerçekleştirim

import heapq


def dijkstra(cizge: dict[str, list[tuple[str, int]]],
             kaynak: str) -> tuple[dict[str, float], dict[str, str | None]]:
    """(uzaklıklar, önceki düğümler) döndürür. Ağırlıklar negatif olmamalıdır."""
    uzaklik: dict[str, float] = {d: float("inf") for d in cizge}
    onceki: dict[str, str | None] = {d: None for d in cizge}
    uzaklik[kaynak] = 0
    kuyruk: list[tuple[float, str]] = [(0, kaynak)]
    kesinlesen: set[str] = set()

    while kuyruk:
        d, v = heapq.heappop(kuyruk)
        if v in kesinlesen:            # eskimiş kayıt: atla
            continue
        kesinlesen.add(v)
        for komsu, agirlik in cizge[v]:
            if d + agirlik < uzaklik[komsu]:
                uzaklik[komsu] = d + agirlik
                onceki[komsu] = v
                heapq.heappush(kuyruk, (uzaklik[komsu], komsu))
    return uzaklik, onceki


uzaklik, onceki = dijkstra(cizge, "A")
print(uzaklik)
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

A’dan D’ye doğrudan giden yol A→B→D ile 14 uzunluğundadır; algoritma A→C→E→D yolunu 9 ile bulur. Açgözlü seçim, daha uzun görünen bir başlangıcın toplamda daha kısa olmasını engellemez — çünkü seçim kenarlara değil, birikmiş uzaklıklara bakar.

Yolu Geri Kurmak

Uzaklık tek başına yetmez; hangi yoldan gidildiği de gerekir. onceki sözlüğü bu bilgiyi taşır: her düğüm, kendisine en kısa yolla gelinen düğümü işaret eder.

def yolu_kur(onceki: dict[str, str | None], hedef: str) -> list[str]:
    yol: list[str] = []
    dugum: str | None = hedef
    while dugum is not None:
        yol.append(dugum)
        dugum = onceki[dugum]
    return yol[::-1]


print(yolu_kur(onceki, "F"))       # ['A', 'C', 'E', 'D', 'F']
print(yolu_kur(onceki, "B"))       # ['A', 'B']

Bu işaretçiler bir en kısa yol ağacı oluşturur: kaynaktan tüm düğümlere giden en kısa yolları birlikte kodlayan, kök kaynağa oturan bir ağaç.

Maliyet

Her düğüm en çok bir kez kesinleşir; her kenar en çok bir gevşetme ve bir kuyruk ekleme üretir. İkili yığınla:

$$O\big((V + E)\log V\big)$$

Kuyrukta aynı düğümün birden çok kaydı bulunabilir — buradaki gerçekleştirim eskimiş kayıtları çıkarırken atlar. Bu tembel silme, azaltma işlemi olan bir öncelik kuyruğu gerektirmeden aynı asimptotik sınırı verir ve kodu belirgin biçimde kısaltır.

Yoğun çizgelerde ($E \approx V^2$) kuyruk yerine dizi taraması kullanan değişke $O(V^2)$’dir ve daha hızlı olabilir. Fibonacci yığını kullanan kuramsal değişke $O(E + V \log V)$ verir; sabitleri büyük olduğu için pratikte seyrek görülür.

Sık Kullanılan Değişkeler

Temel yapı küçük değişikliklerle farklı sorulara uyarlanır.

Tek hedef için erken çıkış. Yalnızca belirli bir düğüme uzaklık gerekiyorsa, o düğüm kuyruktan çıkarıldığı anda durulabilir; değeri o noktada kesinleşmiştir. Kalan düğümler hiç işlenmez.

Çok kaynaklı arama. “Herhangi bir depoya en yakın uzaklık” gibi sorularda, tüm kaynaklar başlangıçta sıfır uzaklıkla kuyruğa konur. Bu, tek bir yapay kaynağın tüm depolara sıfır ağırlıklı kenar çektiği çizgeye denktir; Veri Yapıları kursundaki çok kaynaklı enine aramanın ağırlıklı karşılığıdır.

Ulaşılamayan düğümler. Kaynaktan erişilemeyen düğümlerin uzaklığı sonsuz kalır. Sonucu kullanan kodun bu değeri sınaması gerekir; sonsuzu sayısal bir uzaklık gibi işleme sokmak sessiz hatalara yol açar.

Ağırlıkların yalnızca 0 ve 1 olması. Bu durumda öncelik kuyruğu yerine çift uçlu kuyruk yeter: sıfır ağırlıklı kenar başa, bir ağırlıklı kenar sona eklenir. Maliyet $O(V + E)$’ye iner — logaritmik çarpan, ağırlık çeşitliliğinin bedelidir.

Negatif Ağırlık Kısıtı

Algoritmanın doğruluğu, “kesinleşen düğümün değeri bir daha düşemez” varsayımına dayanıyordu. Negatif ağırlıklı bir kenar bu varsayımı bozar.

negatifli = {
    "A": [("B", 1), ("C", 2)],
    "B": [("D", 1)],
    "C": [("B", -2)],
    "D": [],
}

print(dijkstra(negatifli, "A")[0])
# {'A': 0, 'B': 0, 'C': 2, 'D': 2}      — D yanlış: gerçek uzaklık 1

B düğümü, ağırlığı 1 olan doğrudan kenarla kesinleştirilir ve D bu değer üzerinden 2 olarak gevşetilir. Sonra C işlenir ve A→C→B yolunun $2 + (-2) = 0$ olduğu ortaya çıkar; B’nin değeri düzelir ama B kesinleşmiş sayıldığı için çıkan kenarları bir daha gevşetilmez. D eski değerinde kalır.

Algoritma hata vermez; sessizce yanlış sonuç üretir. Bu, ön koşulları belgelemenin neden bir biçimsellik olmadığını gösteren örneklerden biridir.

Negatif ağırlıklarla çalışan algoritma sonraki dersin konusudur.

Özet

• Tek kaynaktan en kısa yol problemi, ağırlıklı çizgede kaynaktan tüm düğümlere en düşük toplam maliyetli yolları ister.
• Gevşetme, bir düğümün tahmini uzaklığını bulunan daha iyi bir yolla düşürür ve her tahmin gerçek bir yola karşılık gelir.
• Dijkstra, kesinleşmemiş düğümler arasında en küçük tahminliyi seçer; doğruluğu ağırlıkların negatif olmamasına dayanır.
• Öncelik kuyruklu gerçekleştirim $O((V + E)\log V)$’dir; tembel silme, azaltma işlemi gerektirmez.
• Önceki düğüm işaretçileri en kısa yol ağacını kodlar ve yolun geri kurulmasını sağlar.
• Negatif ağırlıkta algoritma hata vermeden yanlış sonuç üretir.

Sonraki Adım

Negatif ağırlıklar gerçek problemlerde ortaya çıkar: para birimi çevrimlerinde kazanç, üretim planında geri kazanım. Sonraki ders, açgözlü seçimden vazgeçip tüm kenarları tekrar tekrar gevşeten Bellman–Ford algoritmasını kuracak ve negatif döngülerin neden problemi tanımsız kıldığını gösterecek.