Bellman-ford算法 學習筆記

       Bellman-Ford算法與Dijkstra算法思想一樣，用于求解單源點最短路徑問題。Bellman-ford算法除了可求解邊權均非負的問題外，關鍵是還可以解決存在負權邊的問題，而Dijkstra算法隻能處理邊權非負的問題，是以 Bellman-Ford算法的适用面要廣泛一些。但是，原始的Bellman-Ford算法時間複雜度為 O（VE）,比Dijkstra算法的時間複雜度高，就連經典的《算法導論》也隻介紹了基本的Bellman-Ford算法，事實上，有多種形式的Bellman-Ford算法的優化實作。這些優化實作在時間效率上得到相當提升，例如近一兩年被熱捧的SPFA（Shortest-Path Faster Algoithm 更快的最短路徑算法）算法的時間效率甚至由于Dijkstra算法，本文試圖對Bellman-Ford算法做一個比較全面的介紹。

Bellman-Ford算法思想

    Bellman-Ford算法能在更普遍的情況下（存在負權邊）解決單源點最短路徑問題。對于給定的帶權（有向或無向）圖 G=（V,E），其源點為s，對圖G運作Bellman-Ford算法的結果是一個布爾值，表明圖中是否存在着一個從源點s可達的負權回路。若不存在這樣的回路，算法将給出從源點s到 圖G的任意頂點v的最短路徑dist[v]。

Bellman-Ford算法流程分為三個階段：

（1）    初始化：将除源點外的所有頂點的最短距離估計值 dist[v] ←+∞, dist[s] ←0;

（2）    疊代求解：反複對邊集E中的每條邊進行松弛操作，使得頂點集V中的每個頂點v的最短距離估計值逐漸逼近其最短距離；（運作|v|-1次）

（3）    檢驗負權回路：判斷邊集E中的每一條邊的兩個端點是否收斂。如果存在未收斂的頂點，則算法傳回false，表明問題無解；否則算法傳回true，并且從源點可達的頂點v的最短距離儲存在 dist[v]中。

Bellman-Ford(G,w,s) ：boolean   //圖G ，邊集 函數 w ，s為源點

1        for each vertex v ∈ V（G） do        //初始化 1階段

2            dist[v] ←+∞

3        dist[s] ←0;                             //1階段結束

4        for i=1 to |v|-1 do               //2階段開始，雙重循環。

5           for each edge（u,v） ∈E(G) do //邊集數組要用到，窮舉每條邊。

6              If dist[v]> dist[u]+ w(u,v) then      //松弛判斷

7                 dist[v]=dist[u]+w(u,v)               //松弛操作   2階段結束

8        for each edge（u,v） ∈E(G) do

9            If dist[v]> dist[u]+ w(u,v) then

10            Exit false

11    Exit true

下面給出描述性證明：

   首先指出，圖的任意一條最短路徑既不能包含負權回路，也不會包含正權回路，是以它最多包含|v|-1條邊。

   其次，從源點s可達的所有頂點如果 存在最短路徑，則這些最短路徑構成一個以s為根的最短路徑樹。Bellman-Ford算法的疊代松弛操作，實際上就是按頂點距離s的層次，逐層生成這棵最短路徑樹的過程。

在對每條邊進行1 遍松弛的時候，生成了從s出發，層次至多為1的那些樹枝。也就是說，找到了與s至多有1條邊相聯的那些頂點的最短路徑；對每條邊進行第2遍松弛的時候，生成了第2層次的樹枝，就是說找到了經過2條邊相連的那些頂點的最短路徑……。因為最短路徑最多隻包含|v|-1 條邊，是以，隻需要循環|v|-1 次。

每實施一次松弛操作，最短路徑樹上就會有一層頂點達到其最短距離，此後這層頂點的最短距離值就會一直保持不變，不再受後續松弛操作的影響。（但是，每次還要判斷松弛，這裡浪費了大量的時間，怎麼優化？單純的優化是否可行？）

如果沒有負權回路，由于最短路徑樹的高度最多隻能是|v|-1，是以最多經過|v|-1遍松弛操作後，所有從s可達的頂點必将求出最短距離。如果 dist[v]仍保持 +∞，則表明從s到v不可達。

如果有負權回路，那麼第 |v|-1 遍松弛操作仍然會成功，這時，負權回路上的頂點不會收斂。

基本 Bellman-Ford 算法的c語言實作:

#include<stdio.h>

#include<stdlib.h>

#define MAX 0x3f3f3f3f

#define N 1010

int nodenum, edgenum, original; //點，邊，起點

typedef struct Edge //邊

{

    int u, v;

    int cost;

}Edge;

Edge edge[N];

int dist[N], pre[N];

bool Bellman_Ford()

{

    for(int i = 1; i <= nodenum; ++i) //初始化

        dis[i] =  MAX;

    dist[original] = 0;

    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;

}

基本算法之上的優化

    分析 Bellman-Ford算法，不難看出，外層循環（疊代次數）|v|-1實際上取得是上限。由上面對算法正确性的證明可知，需要的疊代遍數等于最短路徑樹的高度。如果不存在負權回路，平均情況下的最短路徑樹的高度應該遠遠小于 |v|-1，在此情況下，多餘最短路徑樹高的疊代遍數就是時間上的浪費，由此，可以依次來實施優化。

從細節上分析，如果在某一遍疊代中，算法描述中第7行的松弛操作未執行，說明該遍疊代所有的邊都沒有被松弛。至此後，邊集中所有的邊都不需要再被松弛，進而可以提前結束疊代過程。這樣，優化的措施就非常簡單了。

設定一個布爾型标志變量 is_relaxed，初值為false。在内層循環中，僅當有邊被成功松弛時，将 is_relaxed 設定為true。如果沒有邊被松弛，則提前結束外層循環。這一改進可以極大的減少外層循環的疊代次數。優化後的 bellman-ford函數如下。

function bellmanford(s:longint):boolean;

     begin

        for i:=1 to nv do

          dist[i]:=max;

        dist[s]:=0;

        for i:=1 to nv-1 do

         begin

         is_relaxed:=false;

          for j:=1 TO ne do

          if(dist[edges[j].s]<max) and (dist[edges[j].e]>dist[edges[j].s]+edges[j].w)

               then begin

dist[edges[j].e]:=dist[edges[j].s]+edges[j].w ;

is_relaxed:=true;

                         end;

                if not is_relaxed then break;

end;

        for i:=1 to ne do

          if dist[edges[j].e]>dist[edges[j].s]+edges[j].w then exit(false);

        exit(true);

     end;

優化後的算法在處理有負權回路的測試資料時，由于每次都會有邊被松弛，是以relaxed每次都會被置為true，因而不可能提前終止外層循環。這對應了最壞情況，其時間複雜度仍舊為O(VE)。

優化後的算法的時間複雜度已經和用二叉堆優化的Dijkstra算法相近了，而編碼的複雜程度遠比後者低。加之Bellman-Ford算法能處理各種邊值權情況下的最短路徑問題，是以還是很不錯的。

​