Bellman-Ford算法（最短路徑）

 dijkstra算法是處理單源最短路徑的有效算法，但它局限于邊的權值非負的情況，若圖中出現權值為負的邊，dijkstra算法就會失效，求出的最短路徑就可能是錯的。

這時候，就需要使用其他的算法來求解最短路徑，bellman-ford算法就是其中最常用的一個。該算法由美國數學家理查德?貝爾曼（richard bellman, 動态規劃的提出者）和小萊斯特?福特（lester ford）發明。

适用條件&範圍：

單源最短路徑(從源點s到其它所有頂點v);

有向圖&無向圖(無向圖可以看作(u,v),(v,u)同屬于邊集e的有向圖);

邊權可正可負(如有負權回路輸出錯誤提示);

差分限制系統;

bellman-ford算法的流程如下：

給定圖g(v, e)（其中v、e分别為圖g的頂點集與邊集），源點s，數組distant[i]記錄從源點s到頂點i的路徑長度，初始化數組distant[n]為, distant[s]為0；

以下操作循環執行至多n-1次，n為頂點數：

對于每一條邊e(u, v)，如果distant[u] + w(u, v) < distant[v]，則另distant[v] = distant[u]+w(u, v)。w(u, v)為邊e(u,v)的權值；

若上述操作沒有對distant進行更新，說明最短路徑已經查找完畢，或者部分點不可達，跳出循環。否則執行下次循環；

為了檢測圖中是否存在負環路，即權值之和小于0的環路。對于每一條邊e(u, v)，如果存在distant[u] + w(u, v) < distant[v]的邊，則圖中存在負環路，即是說改圖無法求出單源最短路徑。否則數組distant[n]中記錄的就是源點s到各頂點的最短路徑長度。

可知，bellman-ford算法尋找單源最短路徑的時間複雜度為o(v*e).

bellman－ford算法可以大緻分為三個部分

第一，初始化所有點。每一個點儲存一個值，表示從原點到達這個點的距離，将原點的值設為0，其它的點的值設為無窮大（表示不可達）。

第二，進行循環，循環下标為從1到n－1（n等于圖中點的個數）。在循環内部，周遊所有的邊，進行松弛計算。

第三，周遊途中所有的邊（edge（u，v）），判斷是否存在這樣情況：

d（v） > d (u) + w(u,v)

則傳回false，表示途中存在從源點可達的權為負的回路。

之是以需要第三部分的原因，是因為，如果存在從源點可達的權為負的回路。則 應為無法收斂而導緻不能求出最短路徑。 

測試代碼如下：（下面為有向圖的bellman-ford算法。。。。。）

[cpp]

#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;  

測試資料：

4 6 1

1 2 20

1 3 5

4 1 -200

2 4 4

4 2 4

3 4 2

和：

1 2 2

4 1 10