Bellman-Ford Algoritması
- Ortaya koyan
- Richard Bellman and Lester R. Ford
- Yıl
- 1956
- Tür
- algorithm
- Aile
- Graph Algorithms
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Richard Bellman ve Lester R. Ford tarafından 1950'lerde geliştirilen Bellman-Ford Algoritması, negatif kenar ağırlıklarına sahip ağırlıklı graflarda en kısa yolları hesaplamak için temel bir algoritmadır.
Dijkstra algoritmasının aksine, negatif ağırlıkları doğru bir şekilde ele alır ve negatif ağırlıklı döngülerin varlığını tespit edebilir.
Yöntemin mantığı
Algoritma, kenarları yinelemeli olarak gevşeterek çalışır: her kenar için, o kenardan geçmenin hedefe mevcut bilinen en iyi yoldan daha kısa bir yol sunduğunu kontrol eder. Bu işlemi, V köşe sayısı olmak üzere, tüm kenarlar için V-1 kez tekrarlayarak, algoritma negatif ağırlıklar olsa bile en kısa yolu bulmayı garanti eder. Temel fikir, V köşeli bir graftaki herhangi bir en kısa yolun en fazla V-1 kenar içermesidir; V-1 iterasyondan sonra mesafeler hala iyileşiyorsa, bir negatif döngü bulunmalıdır.
Tarih
Algoritma, Richard Bellman tarafından 1958'de dinamik programlama prensipleri kullanılarak geliştirilmiş, Lester R. Ford ise 1956'da ağ akışları için benzer bir yaklaşım keşfetmiştir. Algoritma 1960'larda daha da geliştirilmiş ve iyileştirilmiş, uygulamaları ağ yönlendirme ve ekonomik uygulamalara kadar genişlemiştir. Modern varyantlar arasında En Kısa Yol Daha Hızlı Algoritması (SPFA) ve belirli graf yapıları için çeşitli optimizasyonlar yer almaktadır, ancak temel Bellman-Ford yaklaşımı algoritma tasarımında klasik bir referans olarak kalmaktadır.
Ne zaman kullanılır?
En kısa yolları negatif kenar ağırlıklarına sahip graflarda hesaplarken Bellman-Ford algoritmasını uygulayın. Döviz arbitrajı tespiti, ağırlıkların negatif olabileceği ağ protokolleri ve negatif maliyetlerin veya ağırlıkların anlamlı olduğu herhangi bir uygulama için esastır. Tüm ağırlıklar negatif değilse, daha verimli olduğu için Dijkstra algoritmasını kullanın. Yolları hesaplamadan negatif döngüleri tespit etmek için bu algoritma da uygundur.
Sınırlar ve dikkat edilmesi gerekenler
- Negatif ağırlıklar için Dijkstra'dan daha yavaştır: O(VE) - O((V+E)logV)
- Seyrek graflar için diğer algoritmalara göre daha az verimlidir
- Tüm kenarların açıkça listelenmesini gerektirir, bu da onu örtük veya dinamik graflar için daha az uygun hale getirir
- Hesaplamayı hızlandırmak için herhangi bir sezgisel rehberlik mevcut değildir
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Negatif kenar ağırlıklarına sahip grafları doğru bir şekilde işler
- Negatif ağırlıklı döngüleri tespit eder, hatalı en kısa yol sonuçlarını önler
- Bazı gelişmiş en kısa yol algoritmalarından daha basit anlaşılır ve uygulanır
- O(VE) zamanda en kısa yolları bulmayı garanti eder
- Yönlü ve yönsüz graflarda çalışır (yönsüz graflarda dikkatli olunmalıdır)
Uygulama alanları
- Döviz arbitrajı tespiti: döviz kuru graflarında kârlı döngüleri belirleme
- Ağ yönlendirme protokolleri: bağlantı maliyetlerinin değişebileceği veya negatif olabileceği yerlerde en kısa yolları hesaplama
- Oyun teorisi: ceza kenarları veya indirim faktörleri ile en kısa yol problemlerini çözme
- Robotik: itici kuvvetlere (negatif ağırlıklar) sahip ortamlarda yol planlama
- Ekonomik sevkiyat: negatif terimler içeren maliyet fonksiyonları ile güç üretimini optimize etme
- Telekomünikasyon: bağlantı ağırlıklarının gecikme veya kalite metriklerini temsil ettiği durumlarda en uygun rotaları bulma
Nasıl çalışır?
Nasıl çalışır?
Kaynak düğümün uzaklığını sıfır, diğer tüm uzaklıkları sonsuz olarak ayarlayın; isteğe bağlı olarak tüm öncülleri boş olarak ayarlayın.
V-1 kez tekrarlayın: her (u, v) kenarı için w ağırlığıyla, eğer uzaklık[u] + w, uzaklık[v]'den küçükse, uzaklık[v]'yı ve v'nin öncülünü güncelleyin.
Tüm kenarları bir kez daha kontrol edin; herhangi bir uzaklık iyileşirse, bir negatif ağırlıklı döngü mevcuttur. Hata döndürün veya uygun şekilde döngüyü tanımlayın.
Sık yapılan hatalar
- Negatif döngüleri tespit etmek için ek iterasyonu yapmayı unutmak
- Algoritmanın negatif kenarlara sahip yönsüz graflarda doğru çalıştığını varsaymak (sanal negatif döngüler oluşturabilir)
- Dijkstra'nın yeterli olduğu durumlarda algoritmayı kullanmak, gereksiz performans kaybına yol açar
Sık sorulan sorular
Algoritmanın neden tam olarak V-1 iterasyona ihtiyacı var?
V köşeli bir graftaki herhangi bir yol en fazla V-1 kenar içerir. V-1 kez yineleyerek, algoritma mesafe bilgilerinin tüm graf boyunca yayılmasına izin verir. V'inci bir iterasyon yalnızca bir negatif döngü varsa mesafeleri iyileştirecektir.
Algoritma negatif döngüleri nasıl tespit edebilir?
V-1 iterasyonu tamamladıktan sonra, bir gevşetme geçişi daha yapın. Herhangi bir uzaklık azalırsa, bir negatif döngü mevcuttur. Döngüye dahil olan düğümler, öncül işaretçiler kullanılarak geriye izleme yoluyla belirlenebilir.
Zaman karmaşıklığı nedir ve Dijkstra ile nasıl karşılaştırılır?
Bellman-Ford, V köşe ve E kenar olmak üzere O(VE) zamanda çalışır. Dijkstra, ikili yığın ile O((V+E)logV) zamanda çalışır. Bellman-Ford daha yavaştır ancak negatif ağırlıkları işler; Dijkstra daha hızlıdır ancak negatif olmayan ağırlıklar gerektirir.
Bellman-Ford negatif ağırlıklı yönsüz graflarda çalışabilir mi?
Teknik olarak evet, ancak kenarların çift yönlü doğası nedeniyle yapay negatif döngüler oluşturabilir. Sonuçları doğru yorumlamak için özel dikkat gerekir. Yönsüz graflar için alternatif yaklaşımları düşünün.
İlgili yöntemler
Kaynaklar
Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90.
DOI kaynağını açKopyalandı.Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923.
Yayın kaynağını açKopyalandı.