Bellman-Ford算法

Bellman-Ford算法

Bellman - ford算法是求含負權圖的單源最短路徑的一種算法,效率較低,代碼難度較小。其原理為連續進行鬆弛,在每次鬆弛時把每條邊都更新一下,若在n-1次鬆弛後還能更新,則說明圖中有負環,因此無法得出結果,否則就完成。

基本介紹

  • 中文名:貝爾曼-福特算法
  • 外文名:Bellman - Ford algorithm
  • 算法類別:求含負權的單源最短路徑算法
  • 缺點:效率很低  O(NM)
  • 優點:有較高實用性,適用於負權圖。
  • 最佳化:SPFA算法[佇列最佳化]
  • 特色:判斷並找出負權迴路
介紹,適用條件,算法描述,描述性證明,偽代碼,參考代碼,引申內容,算法流程,算法代碼,算法的最佳化,

介紹

Dijkstra算法無法判斷含負權邊的圖的最短路。如果遇到負權,在沒有負權迴路(迴路的權值和為負,即便有負權的邊)存在時,也可以採用Bellman - Ford算法正確求出最短路徑。
Bellman-Ford算法能在更普遍的情況下(存在負權邊)解決單源點最短路徑問題。對於給定的帶權(有向或無向)圖 G=(V,E), 其源點為s,加權函式 w是 邊集 E 的映射。對圖G運行Bellman - Ford算法的結果是一個布爾值,表明圖中是否存在著一個從源點s可達的負權迴路。若不存在這樣的迴路,算法將給出從源點s到 圖G的任意頂點v的最短路徑d[v]。

適用條件

1.單源最短路徑(從源點s到其它所有頂點v);
2.有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬於邊集E的有向圖);
3.邊權可正可負(如有負權迴路輸出錯誤提示);

算法描述

1,.初始化:將除源點外的所有頂點的最短距離估計值 d[v] ——>+∞, d[s]——>0;
2.疊代求解:反覆對邊集E中的每條邊進行鬆弛操作,使得頂點集V中的每個頂點v的最短距離估計值逐步逼近其最短距離;(運行|v|-1次)
3.檢驗負權迴路:判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點,則算法返回false,表明問題無解;否則算法返回true,並且從源點可達的頂點v的最短距離保存在 d[v]中。

描述性證明

首先指出,圖的任意一條最短路徑既不能包含負權迴路,也不會包含正權迴路,因此它最多包含|v|-1條邊。
其次,從源點s可達的所有頂點如果 存在最短路徑,則這些最短路徑構成一個以s為根的最短路徑樹。Bellman-Ford算法的疊代鬆弛操作,實際上就是按每個點實際的最短路徑[雖然我們還不知道,但它一定存在]的層次,逐層生成這棵最短路徑樹的過程。
注意,每一次遍歷,都可以從前一次遍歷的基礎上,找到此次遍歷的部分點的單源最短路徑。如:這是第i次遍歷,那么,通過數學歸納法,若前面單源最短路徑層次為1~(i-1)的點全部已經得到,而單源最短路徑層次為i的點,必定可由單源最短路徑層次為i-1的點集得到,從而在下一次遍歷中充當前一次的點集,如此往復疊代,[v]-1次後,若無負權迴路,則我們已經達到了所需的目的--得到每個點的單源最短路徑。[注意:這棵樹的每一次更新,可以將其中的某一個子樹接到另一個點下]
反之,可證,若存在負權迴路,第[v]次遍歷一定存在更新,因為負權迴路的環中,必定存在一個“斷點”,可用數學手段證明。
最後,我們在第[v]次更新中若沒有新的鬆弛,則輸出結果,若依然存在鬆弛,則輸出‘CAN'T'表示無解。同時,我們還可以通過“斷點”找到負權迴路。

偽代碼

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
時間複雜度
算法時間複雜度O(VE)。因為算法簡單,適用範圍又廣,雖然複雜度稍高,仍不失為一個很實用的算法。

參考代碼

PASCAL
{單源最短路徑的Bellman-ford算法
執行v-1次,每次對每條邊進行鬆弛操作
如有負權迴路則輸出"Error!!"}
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.
Matlab
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
C++
#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;  }  

引申內容

SPFA算法
SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一種佇列最佳化,減少了不必要的冗餘計算。

算法流程

算法大致流程是用一個佇列來進行維護。 初始時將源加入佇列。 每次從佇列中取出一個元素,並對所有與他相鄰的點進行鬆弛,若某個相鄰的點鬆弛成功,則將其入隊。 直到佇列為空時算法結束。

算法代碼

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;

算法的最佳化

分析 Bellman-Ford算法,不難看出,外層循環(疊代次數)|v|-1實際上取得是上限。由上面對算法正確性的證明可知,需要的疊代遍數等於最短路徑樹的高度。如果不存在負權迴路,平均情況下的最短路徑樹的高度應該遠遠小於 |v|-1,在此情況下,多餘最短路徑樹高的疊代遍數就是時間上的浪費,由此,可以依次來實施最佳化。
從細節上分析,如果在某一遍疊代中,算法描述中第7行的鬆弛操作未執行,說明該遍疊代所有的邊都沒有被鬆弛。可以證明(怎么證明?):至此後,邊集中所有的邊都不需要再被鬆弛,從而可以提前結束疊代過程。這樣,最佳化的措施就非常簡單了。
設定一個布爾型標誌變數 relaxed,初值為false。在內層循環中,僅當有邊被成功鬆弛時,將 relaxed 設定為true。如果沒有邊被鬆弛,則提前結束外層循環。這一改進可以極大的減少外層循環的疊代次數。最佳化後的 bellman-ford函式如下。
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;
這樣看似平凡的最佳化,會有怎樣的效果呢?有研究表明,對於隨機生成數據的平均情況,時間複雜度的估算公式為
1.13|E| if |E|<|V|
0.95*|E|*lg|V| if |E|>|V|
最佳化後的算法在處理有負權迴路的測試數據時,由於每次都會有邊被鬆弛,所以relaxed每次都會被置為true,因而不可能提前終止外層循環。這對應了最壞情況,其時間複雜度仍舊為O(VE)。
最佳化後的算法的時間複雜度已經和用二叉堆最佳化的Dijkstra算法相近了,而編碼的複雜程度遠比後者低。加之Bellman-Ford算法能處理各種邊值權情況下的最短路徑問題,因而還是非常優秀的。

相關詞條

熱門詞條

聯絡我們