Bellman–Ford Algoritması

Dijkstra, bir düğümü kesinleştirdikten sonra bir daha ona dönmüyordu; bu, ağırlıkların negatif olmamasına dayanan bir kazançtı. Negatif ağırlık varsa, bir düğümün değeri sonradan düşebilir ve tek geçiş yetmez.

Bellman–Ford bu varsayımdan vazgeçer: hiçbir düğümü kesinleştirmez, tüm kenarları tekrar tekrar gevşetir.

Algoritma

Kaynak dışındaki tüm uzaklıklar sonsuzdur. Ardından tüm kenarlar üzerinden $V-1$ geçiş yapılır; her geçişte her kenar bir kez gevşetilir.

def bellman_ford(cizge: dict[str, list[tuple[str, int]]],
                 kaynak: str) -> tuple[dict[str, float], bool]:
    """(uzaklıklar, negatif döngü var mı) döndürür."""
    uzaklik: dict[str, float] = {d: float("inf") for d in cizge}
    uzaklik[kaynak] = 0
    kenarlar = [(v, w, a) for v in cizge for w, a in cizge[v]]

    for _ in range(len(cizge) - 1):
        degisim = False
        for v, w, agirlik in kenarlar:
            if uzaklik[v] + agirlik < uzaklik[w]:
                uzaklik[w] = uzaklik[v] + agirlik
                degisim = True
        if not degisim:                 # erken çıkış: hiçbir şey iyileşmedi
            break

    for v, w, agirlik in kenarlar:      # bir geçiş daha hâlâ iyileştiriyorsa
        if uzaklik[v] + agirlik < uzaklik[w]:
            return uzaklik, True
    return uzaklik, False


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

print(bellman_ford(negatifli, "A"))
# ({'A': 0, 'B': 0, 'C': 2, 'D': 1}, False)

Önceki dersin Dijkstra ile yanlış hesapladığı D uzaklığı burada doğru çıkar: 1. Fark, B’nin değeri düştükten sonra çıkan kenarlarının yeniden gevşetilmesidir.

Aynı algoritma negatif ağırlık olmayan çizgelerde de doğrudur; Dijkstra’nın üstünlüğü doğrulukta değil hızdadır.

Neden $V-1$ Geçiş

Gerekçe, yolun kenar sayısı üzerinden tümevarımdır.

İddia: $k$’ıncı geçişten sonra, en çok $k$ kenar kullanan tüm en kısa yollar doğru hesaplanmıştır.

Taban durumu $k = 0$’dır: kaynağın uzaklığı sıfırdır. Adım için, en çok $k+1$ kenarlık bir en kısa yolun son kenarı $(v, w)$ olsun. Yolun v‘ye kadarki bölümü en çok $k$ kenar kullanır ve tümevarım varsayımıyla $k$’ıncı geçişten sonra doğrudur; $k+1$’inci geçişte bu kenar gevşetildiğinde w de doğru değerini alır.

Negatif döngü yoksa hiçbir en kısa yol bir düğümü iki kez ziyaret etmez; dolayısıyla en çok $V-1$ kenar içerir. Bu yüzden $V-1$ geçiş yeterlidir.

Erken çıkış, pratikte geçiş sayısını belirgin biçimde azaltır: bir geçişte hiçbir değer iyileşmediyse sonraki geçişler de iyileştirmez.

Negatif Döngü

$V-1$ geçişten sonra hâlâ gevşeyen bir kenar varsa, kaynaktan ulaşılabilen bir negatif döngü vardır.

donguluu = {
    "A": [("B", 1)],
    "B": [("C", -3)],
    "C": [("B", 1)],           # B → C → B döngüsü: -3 + 1 = -2
}

print(bellman_ford(donguluu, "A")[1])      # True

Böyle bir döngüde problem tanımsızdır: döngü her dolaşıldığında toplam maliyet düşer, dolayısıyla “en kısa yol” diye bir şey yoktur. Tespit, hesaplanan değerleri kurtarmak için değil, sorunun kendisini bildirmek için yapılır.

Tespit yeteneği bir yan ürün değil, algoritmanın başlıca kullanım nedenlerinden biridir. Klasik uygulama, çevrim kazançlarının tespitidir: kur oranlarının çarpımsal kazancı $-\log$ dönüşümüyle toplamsal maliyete çevrilirse, kazançlı bir çevrim negatif döngü hâline gelir ve algoritma onu bulur.

Etkilenen Düğümleri İşaretlemek

Negatif döngünün varlığını bilmek çoğu zaman yetmez; hangi düğümlerin bundan etkilendiği sorulur. Döngüden ulaşılabilen her düğümün uzaklığı istenildiği kadar küçültülebilir, yani eksi sonsuzdur; geri kalan düğümlerin değerleri ise geçerlidir.

Ayrım, $V-1$ geçiş daha yaparak ve gevşeyen kenarların hedeflerini eksi sonsuz olarak işaretleyerek yapılır.

def bellman_ford_isaretli(cizge: dict[str, list[tuple[str, int]]],
                          kaynak: str) -> dict[str, float]:
    uzaklik: dict[str, float] = {d: float("inf") for d in cizge}
    uzaklik[kaynak] = 0
    kenarlar = [(v, w, a) for v in cizge for w, a in cizge[v]]

    for _ in range(len(cizge) - 1):
        for v, w, agirlik in kenarlar:
            if uzaklik[v] + agirlik < uzaklik[w]:
                uzaklik[w] = uzaklik[v] + agirlik

    for _ in range(len(cizge) - 1):      # eksi sonsuzu yay
        for v, w, agirlik in kenarlar:
            if uzaklik[v] != float("inf") and (
                uzaklik[v] + agirlik < uzaklik[w] or uzaklik[v] == float("-inf")
            ):
                uzaklik[w] = float("-inf")
    return uzaklik


donguluu_genis = {
    "A": [("B", 1)],
    "B": [("C", -3)],
    "C": [("B", 1), ("D", 2)],
    "D": [],
    "E": [("A", 1)],          # kaynaktan ulaşılamaz
}

print(bellman_ford_isaretli(donguluu_genis, "A"))
# {'A': 0, 'B': -inf, 'C': -inf, 'D': -inf, 'E': inf}

Üç ayrı durum aynı sözlükte görünür: geçerli uzaklık (A), negatif döngüden etkilenen düğümler (B, C, D) ve ulaşılamayan düğüm (E). Bir sonucu kullanan kodun üç durumu da ayırt etmesi gerekir.

Maliyet

Her geçişte tüm kenarlar işlenir ve en çok $V-1$ geçiş yapılır:

$$O(V \cdot E)$$

Dijkstra’nın $O((V+E)\log V)$ maliyetiyle karşılaştırıldığında belirgin biçimde pahalıdır. Alan maliyeti $O(V)$’dir.

Ölçüt	Dijkstra	Bellman–Ford
Negatif ağırlık	Kabul etmez	Kabul eder
Negatif döngü	Tespit etmez	Tespit eder
Maliyet	$O((V+E)\log V)$	$O(V \cdot E)$
Yaklaşım	Açgözlü	Yinelemeli gevşetme

Seçim ölçütü nettir: ağırlıklar negatif olamıyorsa Dijkstra, olabiliyorsa Bellman–Ford. Tüm düğüm çiftleri arasındaki uzaklıklar isteniyorsa, her düğümden ayrı çalıştırmak yerine tüm çiftler için tasarlanmış algoritmalar kullanılır; bunlar İleri Algoritmalar kursunun konusudur.

Çevrimsiz Çizgede Daha Ucuz Yol

Çizge yönlü ve çevrimsizse (DAG), döngü olmadığı için gevşetme sırası bir kez doğru seçilirse tek geçiş yeter. Doğru sıra, Veri Yapıları kursundaki topolojik sıralamadır: bir düğüm işlendiğinde, ona gelen tüm kenarlar zaten gevşetilmiştir.

def dag_en_kisa_yol(cizge: dict[str, list[tuple[str, int]]],
                    sira: list[str], kaynak: str) -> dict[str, float]:
    """sira: topolojik sıralama. Maliyet O(V + E)."""
    uzaklik: dict[str, float] = {d: float("inf") for d in cizge}
    uzaklik[kaynak] = 0
    for v in sira:
        if uzaklik[v] == float("inf"):
            continue
        for w, agirlik in cizge[v]:
            if uzaklik[v] + agirlik < uzaklik[w]:
                uzaklik[w] = uzaklik[v] + agirlik
    return uzaklik


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

print(dag_en_kisa_yol(cizge, ["A", "B", "C", "E", "D", "F"], "A"))
# {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20}

Sonuç, Dijkstra’nın aynı çizgede bulduğuyla aynıdır; maliyet ise $O(V + E)$’ye düşer. Üstelik bu yöntem negatif ağırlıkları da kabul eder, çünkü açgözlü bir seçim yapmaz.

Aynı yapı, en uzun yolu bulmak için de kullanılır: karşılaştırma yönü ters çevrilir. Genel çizgelerde en uzun yol problemi zor bir problemdir; çevrimsizlik onu doğrusal hâle getirir. Proje planlamasındaki kritik yol hesabı bu türdendir.

Özet

• Bellman–Ford hiçbir düğümü kesinleştirmez; tüm kenarları $V-1$ geçiş boyunca gevşetir.
• $k$’ıncı geçişten sonra en çok $k$ kenarlık tüm en kısa yollar doğrudur; negatif döngü yoksa en kısa yol en çok $V-1$ kenar içerir.
• $V$’inci geçişte hâlâ gevşeyen bir kenar, kaynaktan ulaşılabilen negatif döngü demektir ve problem tanımsızdır.
• Maliyet $O(V \cdot E)$’dir; erken çıkış pratikte geçiş sayısını azaltır.
• Ağırlıklar negatif olamıyorsa Dijkstra, olabiliyorsa Bellman–Ford seçilir.
• Çevrimsiz çizgelerde topolojik sırayla tek geçiş yeterlidir ve maliyet $O(V + E)$’dir.

Sonraki Adım

İki algoritma da hedefi olmayan aramalar yaptı: kaynaktan tüm düğümlere uzaklık hesaplandı. Belirli bir hedefe gidiliyorsa bu israftır. Sonraki ders, hedefin yönünü bilen bir tahmin işleviyle aramayı daraltan A* algoritmasını ve tahminin hangi koşulda doğruluğu bozmadığını ele alacak.