Bellman–Ford algoritması

Bazı en kısa yol problemlerinde bir yolu ucuzlatan kenarlar vardır: bir geri ödeme, bir yokuş aşağı parça, lehinize bir döviz kuru. Dijkstra algoritması bunlarla başa çıkamaz. Bellman–Ford algoritması çıkar; zekâ yerine sabrı seçerek.

Tek yönlü oklar, bazı negatif kenarlar, düğümlerde şimdiye kadar bulunan uzaklıklar ve kırmızıyla çizilmiş negatif bir döngü bulunan bir graf
Tek yönlü oklar, bazı negatif kenarlar, düğümlerde şimdiye kadar bulunan uzaklıklar ve kırmızıyla çizilmiş negatif bir döngü bulunan bir graf

Fikir

Her en kısa yol algoritması tek bir hamleye dayanır, kenar gevşetmeye: u düğümüne gidip sonra u → v kenarını izlemek, v düğümüne bilinen en iyi yoldan kısaysa onu kullanın. Dijkstra algoritması her kenarı bir kez, yalnızca hiçbir kenar negatif değilken işe yarayan akıllıca bir sırayla gevşetir. Bellman–Ford böyle bir varsayım yapmaz. Her kenarı, sabit herhangi bir sırayla, uzaklıklar değişmeyi bırakana kadar tekrar tekrar gevşetir.

Adım adım

Başlangıca uzaklık 0, diğer tüm düğümlere sonsuz verin. n düğüm için n − 1 kez tekrarlayın: her u → v kenarını dolaşın ve u düğümünün bir uzaklığı varsa kenarı gevşetin. Koca bir geçiş hiçbir şeyi değiştirmezse erken durun. Sonra bir geçiş daha yapın. Hâlâ gevşetilebilen bir kenar varsa başlangıçtan toplamı negatif bir döngüye ulaşılabiliyordur; yoksa her uzaklık en kısadır ve hatırlanan düğümler yolları verir.

Bir örnek

Uzunluğu 4 olan A → B, 5 olan A → C, 2 olan B → D ve −3 olan C → B tek yönlü kenarlarını alın; bu sırayla, A düğümünden başlayarak incelensin. 1. geçiş B düğümüne 4, C düğümüne 5 ve D düğümüne 6 verir, ardından C → B kenarı B düğümünü 5 − 3 = 2'ye düşürür. 2. geçiş D düğümünü 2 + 2 = 4'e düşürür. 3. geçiş hiçbir şeyi değiştirmez, yani yanıt B 2, C 5, D 4'tür. Dijkstra algoritması negatif kenarı görmeden önce B düğümünü 4'te, D düğümünü 6'da kesinleştirirdi. Uzunluğu −4 olan bir D → C kenarı ekleyin; C → B → D → C döngüsünün toplamı −5 olur: her geçiş uzaklıkları yeniden düşürür ve kontrol geçişi bunu bildirir.

n − 1 geçiş neden yeter

Bir en kısa yol, varsa, hiçbir düğümü tekrarlamaz, bu yüzden en fazla n − 1 kenarı vardır. Bir geçişte her kenarı gevşetmek, kenarların sırası ne olursa olsun, doğru bilinen her en kısa yolu bir kenar daha uzatır. Böylece k. geçişten sonra en fazla k kenarlı tüm en kısa yollar doğrudur, n − 1 geçişten sonra da hepsi. Yine de sıra hız için önemlidir: iyi bir sırayla bir ya da iki geçişte bitebilir.

Tarihçe ve kullanım alanları

Alfonso Shimbel yöntemi 1955'te, Lester Ford Jr. 1956'da, Edward F. Moore 1957'de ve Richard Bellman 1958'de tanımladı; yöntem bunlardan ikisinin, Bellman ile Ford'un adını taşır. Geçişleri her yönlendirici kendi başına çalıştırabilir; bu da onu RIP gibi uzaklık vektörü yönlendirme protokollerinin temeli yaptı. Finansta döviz kurlarının negatif logaritmasını almak, kârlı bir döviz alım satım turunu negatif bir döngüye çevirir; Bellman–Ford da bunu bulabilir.

Alfred Eisenstaedt’ın 1962’de fotoğrafladığı Richard Bellman. En kısa yol yöntemini Shimbel, Ford ve Moore’dan sonra, 1958’de yayımladı.
Alfred Eisenstaedt’ın 1962’de fotoğrafladığı Richard Bellman. En kısa yol yöntemini Shimbel, Ford ve Moore’dan sonra, 1958’de yayımladı.

Keşfedin

Uygulamayı açın ve Adım'a basın. Her kenar tek yönlüdür ve bazı uzunluklar negatiftir. Her adım sabit bir sırayla bir kenarı inceler; kutucuklar geçişi ve o geçişin kaç uzaklığı değiştirdiğini gösterir. Genellikle bir geçiş kısa sürede hiçbir şeyi değiştirmez olur ve arama erken biter. Negatif döngü ekle'yi işaretleyin ve kontrol geçişi döngüyü bulup kırmızıyla çizene kadar uzaklıkların geçiş geçiş düşüşünü izleyin.

Sık sorulan sorular

Bellman–Ford'un zaman karmaşıklığı nedir?

V düğüm ve E kenar için O(V · E): her biri tüm kenarları inceleyen en fazla V − 1 geçiş. Erken durmayla uygulamada çoğu zaman çok daha hızlıdır ve en iyi durumda tek bir geçiş yeter.

Negatif döngü nedir?

Kenar uzunluklarının toplamı sıfırdan küçük olan bir döngü. Onu tekrar tekrar dolaşmak bir yolu istediğiniz kadar kısaltır; bu yüzden onun üzerinden ulaşılabilen düğümlere en kısa uzaklıklar tanımsızdır.

Bellman–Ford yönsüz graflarda çalışır mı?

Yalnızca hiçbir kenar negatif değilse: yönsüz negatif bir kenardan ileri geri geçilebilir ve bu iki kenarlı bir negatif döngüdür. Negatif olmayan kenarlarla çalışır, ama Dijkstra algoritması daha hızlıdır.

SPFA nedir?

Shortest Path Faster Algorithm, bir kuyruk kullanarak yalnızca uzaklığı yeni değişen düğümlerden çıkan kenarları yeniden inceleyen bir Bellman–Ford sürümüdür. Çoğu zaman çok daha hızlıdır, ama en kötü durumu aynıdır.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Bellman–Ford'u deneyin