bellman-ford

Bellman-ford算法是求含負權圖的單源最短路徑算法,效率很低,但代碼很容易寫。

bellman-ford(貝爾曼—福德)算法介紹

1. 對每條邊進行|V|-1次Relax操作;
所謂Relax就是鬆弛判斷有無負權值的邊
2. 如果存在(u,v)∈E使得dis&#91;u&#93;+w(u,v)<dis&#91;v&#93;,則存在負權迴路;否則dis&#91;v&#93;即為s到v的最短距離,pre&#91;v&#93;為前驅。
Dijkstra算法中不允許邊的權是負權,如果遇到負權,則可以採用Bellman-Ford算法。
Bellman-Ford算法能在更普遍的情況下(存在負權邊)解決單源點最短路徑問題。對於給定的帶權(有向或無向)圖 G=(V,E),其源點為s,加權函式 w是 邊集 E 的映射。對圖G運行Bellman-Ford算法的結果是一個布爾值,表明圖中是否存在著一個從源點s可達的負權迴路。若不存在這樣的迴路,算法將給出從源點s到 圖G的任意頂點v的最短路徑d&#91;v&#93;。

程式代碼

/*如何用bellman-ford判斷存在負權迴路《算法導論》P362(在此算法中未體現,時間複雜度O(VE))*/
#include <iostream>
#include <climits>
using namespace std;
struct node { //記錄每條邊的三個屬性
int a, b, c;
};
node brr&#91;10&#93;;
int arr&#91;10&#93;&#91;10&#93;;
int main(void) {
int m, n, a, b, c;
cin >> m >> n;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
arr&#91;j&#93; = INT_MAX;
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
arr&#91;a&#93; = c;
brr.a = a;
brr.b = b;
brr.c = c;
}
for (int i = 0; i < m-1; i++) //點
for (int j = 0; j < n; j++) { //邊
if (arr&#91;1&#93;.a&#93; != INT_MAX && arr&#91;1&#93;.a&#93;
+ brr&#91;j&#93;.c < arr&#91;1&#93;.b&#93;) //這兒是什麼啊;
arr&#91;1&#93;.b&#93; = arr&#91;1&#93;.a&#93; + brr&#91;j&#93;.c;
}
for (int i = 2; i <= m; i++) {
if (arr&#91;1&#93; == INT_MAX) {
cout << 1 << "-->" << i << ": " << "no exit" << endl;
} else
cout << 1 << "-->" << i << ": " << arr&#91;1&#93; << endl;
}
return 0;
}
/*
6 8
1 3 10
1 5 30
1 6 100
2 3 5
3 4 50
4 6 10
5 4 20
5 6 60
1-->2: no exit!
1-->3: 10
1-->4: 50
1-->5: 30
1-->6: 60
*/
pascal 的代碼:
procedure bellman-ford;
var
i,j:longint;
done:boolean;
dist:array&#91;0..maxn&#93;of longint;
begin
fillchar(dist,sizeof(dist),$f);
dist&#91;1&#93;:=0;
for i:=1 to n-1 do
begin
done:=false;
for j:=1 to m do
with e&#91;j&#93; do
if dist&#91;g1&#93;+c<dist&#91;g2&#93; then
begin
dist&#91;g2&#93;:=dist&#91;g1&#93;+c;
done:=true;
end;
if done=false then break;
end;
ans:=dist&#91;n&#93;;
for j:=1 to m do
with e&#91;j&#93; do
if dist&#91;g1&#93;+c<dist&#91;g2&#93;then
fillchar(ans,4,$f);
end;

相關詞條

相關搜尋

熱門詞條

聯絡我們