Ford-Bellman algoritması
n köşeleri ve m kenarları ve bazı başlangıç köşeleri vG grafiği verilsin > . v köşe noktasından diğer tüm köşelere giden en kısa yolların uzunluklarını bulmak gerekir.
Dijkstra gibi Ford-Bellman 1. köşe ile diğer tüm noktalar arasındaki mesafeyi arar, ancak negatif kenarlarla çalışır güçlü>.
Ford-Bellman algoritmasının kendisi birkaç aşamadan oluşur ( n-1). Her aşamada, grafiğin tüm kenarları incelenir ve algoritma c maliyetinin her bir kenarı (a, b) boyunca gevşemeye çalışır. Sınır boyunca gevşeme — bu, d[a] 'nin anlamını iyileştirme girişimidir; d[b] + c değeri. Aslında bu, kenar ve en üstteki geçerli yanıt.
d dizisi, tıpkı Dijkstra'da olduğu gibi, başlangıç köşe noktasından itibaren en kısa uzunlukları içeren bir dizidir, başlangıçta, koymanız gereken başlangıç köşesi dışında mümkün olduğu kadar büyük sayılarla doldururuz. 0.
Kenarları saklamak için bitişiklik matrisi veya ağırlık matrisi değil, kenarın hangi düğümden ayrıldığını ( from), nereye geldiğini ( to) ve ağırlığı (maliyet).
yapı kenarı {
int from, to, cost;
};
vektör<kenar> kenarlar;
INF sabiti "sonsuz" sayısını belirtir - olası tüm yol uzunluklarını açıkça aşacak şekilde seçilmelidir.
Algoritmanın en basit uygulaması:
d[v] = 0;
için (int i=0; i<n-1; ++i)
için (int j=0; j<m; ++j)
if (d[kenarlar[j].from] <INF)
d[kenarlar[j].to] = min(d[kenarlar[j].to], d[kenarlar[j].from] + kenarlar[j].maliyet);
veya C++11 sözdizimini kullanarak biraz daha kısa:
d[v] = 0;
için (int i=0; i< n-1; ++i)
için (kenar j: kenarlar)
eğer (d[j.from]
İş örneği
Basit yönlendirilmiş bir grafik alın 5 düğüm, 1'e eşit ağırlıkta 4 kenar.
Bu sıradaki kenarların bir listesini sunalım.
4 5 1
3 4 1
2 3 1
1 2 1
En kısa uzunluklar dizisindeki başlangıç değerleri:
| 0 |
bilgi |
bilgi |
bilgi |
bilgi |
burada inf, her zaman kenarın ağırlığından büyük olan eşleşen bir tamsayı olmalıdır.
1. geçişten sonra
| 0 |
1 |
bilgi |
bilgi |
bilgi |
2. geçişten sonra
| 0 |
1 |
2 |
bilgi |
bilgi |
3. geçişten sonra
| 0 |
1 |
2 |
3 |
bilgi |
4. geçişten sonra
| 0 |
1 |
2 |
3 |
4 |
Kenarları 1'den sona doğru beslersek 1. geçişten sonraki en kısa uzunlukları bulabiliriz.
|