Bellman - ford算法是求含負權圖的單源最短路徑的一種算法,效率較低,代碼難度較小。其原理為連續進行鬆弛,在每次鬆弛時把每條邊都更新一下,若在n-1次鬆弛後還能更新,則說明圖中有負環,因此無法得出結果,否則就完成。
基本介紹
- 中文名:貝爾曼-福特算法
- 外文名:Bellman - Ford algorithm
- 算法類別:求含負權圖的單源最短路徑算法
- 缺點:效率很低 O(NM)
- 優點:有較高實用性,適用於負權圖。
- 最佳化:SPFA算法[佇列最佳化]
- 特色:判斷並找出負權迴路
介紹
適用條件
算法描述
描述性證明
偽代碼
bool Bellman-Ford(G,w,s) //圖G ,邊集 函式 w ,s為源點 for each vertex v ∈ V(G): //初始化距離源點距離均為無窮大 d[v] ←+∞ d[s] ←0 //源點距離自身為0 for i = 1 → |V|: //鬆弛操作需要重複多次 for each edge (u,v) ∈ E(G): if d[v] > d[u] + w(u,v): d[v] = d[u] + w(u,v) for each edge(u,v) ∈ E(G): //判斷是否存在負權環路 if d[v] > d[u] + w(u,v): return false return true
參考代碼
const maxn=100; maxe=maxn*(maxn-1)div2;type edge=record a,b,w:integer; end;var edges:array[1..maxe]ofedge; dis:array[1..maxn]ofinteger; pre:array[1..maxn]ofinteger; e,n,s:integer;procedureinit;var i:integer; begin e:=0; assign(input,'g,in');reset(input); readln(n,s); while not eof do begin inc(e); with edges[e] do readln(a,b,w); end; fillchar(dis,sizeof(dis),$7f);//$7f是什麼,解釋替換$7f是127$在pascal中代表後面的數是16進制 dis[s]:=0;pre[s]:=s; end;procedure relax(u,v,w:integer);begin if dis[u]+w<dis[v] then begin dis[v]:=dis[u]+w; pre[v]:=u; end;end;function bellman_ford:boolean;var i,j:integer;begin fori:=1ton-1do forj:=1toedo with edges[j] do relax(a,b,w); for i:=1 to e do with edges[i] do if dis[a]+w<dis[b] then exit(false); exit(true);end;procedureprint_path(i:integer);begin if pre[i]<>s then print_path(pre[i]); write('-->',i);end;procedure show;var i:integer;begin for i:=1 to n do begin write(i:3,':',dis[i]:3,':',s); print_path(i); writeln; end;end;{Main}Begin init; if bellman_ford then show else writeln('Error!!');end.
functionford(d,n,s)%d為已知圖的鄰接矩陣,n為頂點數(各頂點標號為1,2...,n),s為源點標號fori=1:n%初始化dist,predist(i)=inf;%dist(i)為s,i之間的最短路的長度pre(i)=NaN;%pre(i)為s到i的最短路上i的前一個頂點enddist(s)=0;fork=1:n-1fori=1:n%鬆弛操作forj=1:nifd(i,j)~=infifdist(j)>dist(i)+d(i,j)dist(j)=dist(i)+d(i,j);pre(j)=i;endendendendendfori=1:nforj=1:nifd(i,j)~=infifdist(i)+d(i,j)<dist(j)%判斷有無負權迴路error('negetiveweightcircut');endendendenddistpreend
#include<iostream> #include<cstdio> using namespace std; #define MAX 0x3f3f3f3f #define N 1010 int nodenum, edgenum, original; //點,邊,起點 typedef struct Edge //邊 { int u, v; int cost; }Edge; Edge edge[N]; int dis[N], pre[N]; bool Bellman_Ford() { for(int i = 1; i <= nodenum; ++i) //初始化 dis[i] = (i == original ? 0 : MAX); for(int i = 1; i <= nodenum - 1; ++i) for(int j = 1; j <= edgenum; ++j) if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //鬆弛(順序一定不能反~) { dis[edge[j].v] = dis[edge[j].u] + edge[j].cost; pre[edge[j].v] = edge[j].u; } bool flag = 1; //判斷是否含有負權迴路 for(int i = 1; i <= edgenum; ++i) if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost) { flag = 0; break; } return flag; } void print_path(int root) //列印最短路的路徑(反向) { while(root != pre[root]) //前驅 { printf("%d-->", root); root = pre[root]; } if(root == pre[root]) printf("%d\n", root); } int main() { scanf("%d%d%d", &nodenum, &edgenum, &original); pre[original] = original; for(int i = 1; i <= edgenum; ++i) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost); } if(Bellman_Ford()) for(int i = 1; i <= nodenum; ++i) //每個點最短路 { printf("%d\n", dis[i]); printf("Path:"); print_path(i); } else printf("have negative circle\n"); return 0; }
引申內容
算法流程
算法代碼
ProcedureSPFA;Begininitialize-single-source(G,s);initialize-queue(Q);enqueue(Q,s);whilenotempty(Q)dobeginu:=dequeue(Q);foreachv∈adj[u]dobegintmp:=d[v];relax(u,v);if(tmp<>d[v])and(notvinQ)thenenqueue(v);end;end;End;
算法的最佳化
functionbellmanford(s:longint):boolean;beginfori:=1tonvdod[i]:=max;d[s]:=0;fori:=1tonv-1dobeginrelaxed:=false;forj:=1TOnedoif(d[edges[j].s]<>max)and(d[edges[j].e]>d[edges[j].s]+edges[j].w)thenbegind[edges[j].e]:=d[edges[j].s]+edges[j].w;relaxed:=true;end;ifnotrelaxedthenbreak;end;fori:=1tonedoifd[edges[j].e]>d[edges[j].s]+edges[j].wthenexit(false);exit(true);end;