Bellman-Ford Algoritması

#Nasıl çalışır?

Bellman-Ford algoritması, Dijkstra gibi bir başlangıçtan tüm düğümlere en kısa yolları bulur; ama negatif ağırlıklı kenarlarla da doğru çalışır. Negatif ağırlık; geri ödeme, indirim ya da enerji kazancı gibi durumları modeller.

Dijkstra bir düğümü kesinleştirdikten sonra ona bir daha bakmaz. Negatif bir kenar, kesinleşmiş bir düğüme daha sonra daha ucuza ulaşılmasını sağlayabilir; bu yüzden Dijkstra yanlış sonuç verir. Örnek grafta Dijkstra dist[3] = 2 der, oysa 1 → 2 → 3 yolu 4 + (−3) = 1'dir.

Bellman-Ford açgözlü değildir: tüm kenarları V − 1 tur boyunca tekrar tekrar gevşetir. En kısa yol en fazla V − 1 kenar içerdiği için i. turun sonunda en fazla i kenarlı tüm en kısa yollar doğrudur.

V. bir turda hâlâ iyileşen bir mesafe varsa grafta negatif bir döngü vardır: o döngüde dolaştıkça maliyet sürekli düşer ve en kısa yol tanımsız olur. Bellman-Ford bu durumu tespit edebilir.

#Kendin dene

#Adım adım

1. 01dist[başlangıç] = 0, diğer tüm mesafeler ∞.
2. 02V − 1 tur boyunca: her u → v kenarı için dist[u] + w < dist[v] ise dist[v]'yi güncelle.
3. 03Bir turda hiçbir mesafe değişmezse erken dur.
4. 04Son olarak bir tur daha dene: bir mesafe hâlâ düşüyorsa negatif döngü var.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

INF = float("inf")

# Directed edges (from, to, weight); two of them are negative.
EDGES = [(1, 2, 4), (1, 3, 2), (2, 3, -3), (2, 4, 2), (3, 5, 3),
         (3, 6, 5), (4, 7, 2), (5, 4, -1), (5, 7, 4), (6, 7, 1)]
N = 7


def bellman_ford(edges, start):
    """Returns (dist, prev), or None if a negative cycle is reachable."""
    dist = {v: INF for v in range(1, N + 1)}
    prev = {}
    dist[start] = 0
    for _ in range(N - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:
            break  # nothing will change in later rounds either
    for u, v, w in edges:  # one more round: still improving means a negative cycle
        if dist[u] + w < dist[v]:
            return None
    return dist, prev


dist, prev = bellman_ford(EDGES, 1)
print(" ".join(str(dist[v]) for v in range(1, N + 1)))

path = [7]
while path[-1] != 1:
    path.append(prev[path[-1]])
print(" ".join(map(str, reversed(path))))  # uses both negative edges

print("negative cycle" if bellman_ford(EDGES + [(7, 5, -6)], 1) is None else "ok")  # 5 -> 7 -> 5 weighs -2

#Karmaşıklık

Her tur tüm kenarları dolaşır ve en fazla V − 1 tur gerekir; bu yüzden Dijkstra'nın O((V + E) log V) maliyetinden yavaştır. Negatif kenar yoksa Dijkstra tercih edilir. Kuyruk tabanlı bir iyileştirme olan SPFA ortalamada daha hızlıdır ama en kötü durumu aynıdır.

#Ne zaman kullanılır?

Negatif ağırlıklı graflarda en kısa yol, döviz arbitrajı tespiti (kurların logaritmasıyla negatif döngü aramak), mesafe-vektör yönlendirme protokolleri (RIP) ve Johnson algoritmasının ilk adımı Bellman-Ford kullanır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.