- Şu anki
- Uzaklığı var
- Kullanılan kenar
- Yol
- Negatif döngü
Bellman–Ford algoritması
Bir kenarın uzunluğu negatif olduğunda, yani yol sizden geçiş ücreti almak yerine size para ödediğinde, Dijkstra algoritması işe yaramaz. Bellman–Ford algoritması ise yarar: hiçbir şey iyileşmeyene kadar her kenarı tekrar tekrar inceler ve bir döngünün uzaklıkları sonsuza dek düşürdüğünü bile fark edebilir. Oradan başlamak için bir düğüme tıklayın ve geçişleri adım adım izleyin. Aramayı izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Her kenar, okun gösterdiği gibi tek yönlüdür; üzerindeki sayı uzunluğudur ve negatif olabilir. Bir düğümü başlangıç yapmak için ona tıklayın; sonunda başka bir düğüme giden en kısa yolu görmek için tıklamayı Hedef'e çevirin ve o düğüme tıklayın. Her düğümdeki sayı şimdiye kadarki uzaklığıdır. Bellman–Ford'un negatif bir döngüyü nasıl bulduğunu görmek için Negatif döngü ekle'yi işaretleyin. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Bir düğümü başlangıç yapmak için ona tıklayın. Sonunda bir yol görmek için tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayın.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Bellman–Ford'un negatif bir döngüyü bulduğunu görmek için Negatif döngü ekle'yi işaretleyin. Yeni graf, denemeniz için başka bir graf oluşturur.
Bellman–Ford nasıl çalışır
Başlangıca uzaklık 0, diğer tüm düğümlere sonsuz verin. Sonra geçişler yapın: her geçişte her u → v kenarını bir kez inceleyin. u düğümünün bir uzaklığı varsa ve dist(u) artı kenarın uzunluğu dist(v) değerinden küçükse dist(v) değerini düşürün ve oraya giden yol olarak u düğümünü hatırlayın. k. geçişten sonra en fazla k kenar kullanan her en kısa yol bilinir. Bir en kısa yol her düğümden en fazla bir kez geçer, bu yüzden en fazla n − 1 kenarı vardır ve n − 1 geçiş her zaman yeter. Koca bir geçiş hiçbir şeyi değiştirmezse arama erken bitebilir.
Negatif döngüyü bulmak
Bir döngünün kenarlarının toplamı sıfırdan küçükse döngüyü bir kez daha dolaşmak bir yolu her zaman kısaltır, bu yüzden hiç en kısa yol yoktur. Bellman–Ford bunu fark eder: n − 1 geçişten sonra bir geçiş daha hiçbir şeyi değiştirmemelidir. Bir kenar hâlâ gevşetilebiliyorsa başlangıçtan negatif bir döngüye ulaşılabiliyordur ve o kenardan geriye doğru hatırlanan düğümleri izlemek döngünün içine götürür. Uygulamada döngü kırmızıyla çizilir.
Sık sorulan sorular
Bellman–Ford algoritması nedir?
Kenarları negatif uzunluklu olabilen bir grafta bir başlangıçtan diğer tüm düğümlere en kısa yolları bulan bir algoritma. Her kenarı tekrarlanan geçişlerde gevşetir ve başlangıçtan ulaşılabilen negatif bir döngü varsa bunu bildirir.
Dijkstra algoritması negatif kenarlarda neden başarısız olur?
Dijkstra bir düğüm kuyruktaki en yakın düğüm olur olmaz uzaklığını kesinleştirir. Daha sonra bulunan negatif bir kenar, o düğüme daha kısa bir yoldan geri götürebilir; bu yüzden kesinleşen uzaklık yanlış olabilir. Bellman–Ford bir uzaklığı asla erken kesinleştirmez; her kenarı incelemeye devam eder.
Neden n − 1 geçiş?
Bir en kısa yolun bir düğümden iki kez geçmesi hiç gerekmez, bu yüzden en fazla n − 1 kenarı vardır. Her geçiş bilinen en kısa yolları en az bir kenar uzatır, bu yüzden n − 1 geçişten sonra hepsi bulunmuş olur.
Bellman–Ford ne kadar hızlıdır?
Her geçiş E kenarın hepsini inceler ve en fazla V − 1 geçiş vardır, bu yüzden iş V × E ile büyür. Bu Dijkstra algoritmasından yavaştır; Bellman–Ford bu yüzden kenarlar negatif olabildiğinde kullanılır.
Grafım bir yere gönderiliyor mu?
Hayır. Graf tarayıcınızda oluşturulur ve aranır, son ayarlarınız da bu tarayıcının yerel depolamasında kalı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.
Editöre Git