Bellman-Ford Algoritması
Bellman-Ford Algorithm for Shortest Path · Ayrıca şöyle bilinir: Bellman-Ford method, Bellman algorithm
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.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
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.
Güçlü yönler & sınırlılıklar
- 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)
- 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
SSS
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.
Kaynaklar
- Bellman, R. (1958). On a routing problem. Quarterly of Applied Mathematics, 16(1), 87-90. DOI: 10.1090/qam/102435 ↗
- Ford, L. R. (1956). Network Flow Theory. RAND Corporation Paper P-923. link ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Bellman-Ford Algorithm for Shortest Path. ScholarGate. https://scholargate.app/tr/operations-research/bellman-ford-algorithm
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- A* Arama AlgoritmasıYöneylem araştırması↔ karşılaştır
- Dijkstra AlgoritmasıYöneylem araştırması↔ karşılaştır
- Ford-Fulkerson AlgoritmasıYöneylem araştırması↔ karşılaştır