bellman-ford(貝爾曼—福德)算法介紹
1. 對每條邊進行|V|-1次Relax操作;
所謂Relax就是鬆弛判斷有無負權值的邊
2. 如果存在(u,v)∈E使得dis[u]+w(u,v)<dis[v],則存在負權迴路;否則dis[v]即為s到v的最短距離,pre[v]為前驅。
Dijkstra算法中不允許邊的權是負權,如果遇到負權,則可以採用Bellman-Ford算法。
Bellman-Ford算法能在更普遍的情況下(存在負權邊)解決單源點最短路徑問題。對於給定的帶權(有向或無向)圖 G=(V,E),其源點為s,加權函式 w是 邊集 E 的映射。對圖G運行Bellman-Ford算法的結果是一個布爾值,表明圖中是否存在著一個從源點s可達的負權迴路。若不存在這樣的迴路,算法將給出從源點s到 圖G的任意頂點v的最短路徑d[v]。
程式代碼
/*如何用bellman-ford判斷存在負權迴路《算法導論》P362(在此算法中未體現,時間複雜度O(VE))*/
#include <iostream>
#include <climits>
using namespace std;
struct node { //記錄每條邊的三個屬性
int a, b, c;
};
node brr[10];
int arr[10][10];
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[j] = INT_MAX;
for (int i = 0; i < n; i++) {
cin >> a >> b >> c;
arr[a] = 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[1].a] != INT_MAX && arr[1].a]
+ brr[j].c < arr[1].b]) //這兒是什麼啊;
arr[1].b] = arr[1].a] + brr[j].c;
}
for (int i = 2; i <= m; i++) {
if (arr[1] == INT_MAX) {
cout << 1 << "-->" << i << ": " << "no exit" << endl;
} else
cout << 1 << "-->" << i << ": " << arr[1] << 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[0..maxn]of longint;
begin
fillchar(dist,sizeof(dist),$f);
dist[1]:=0;
for i:=1 to n-1 do
begin
done:=false;
for j:=1 to m do
with e[j] do
if dist[g1]+c<dist[g2] then
begin
dist[g2]:=dist[g1]+c;
done:=true;
end;
if done=false then break;
end;
ans:=dist[n];
for j:=1 to m do
with e[j] do
if dist[g1]+c<dist[g2]then
fillchar(ans,4,$f);
end;