--- title: 'Bellman–Ford Algoritması' source: 'https://academia.sh/tr/kurslar/algoritmalar/bellman-ford-algoritmasi' course: Algoritmalar language: tr updated: '2026-08-17T18:07:37+00:00' license: 'CC BY-SA 4.0' --- # Bellman–Ford Algoritması Tüm kenarları yineleyerek gevşetme, kenar sayısına göre tümevarım, negatif döngü tespiti, yönlü çevrimsiz çizgede doğrusal çözüm. 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. ```python 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. ```python 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. ```python 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. ```python 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.