单源最短路——Bellman-Ford算法

1.Dijkstra的局限性

Dijkstra算法是处理单源最短路径的有效算法，但它局限于边的权值非负的情况，若图中出现权值为负的边，Dijkstra算法就会失效，求出的最短路径就可能是错的。

列如以下这个例子：

在这个图中，求从A到C的最短路，如果用Dijkstra根据贪心的思想，选择与A最接近的点C，长度为7，以后不再变化。但是很明显此图最短路为5。归结原因是Dijkstra采用贪心思想，不从整体考虑结果，只从当前情况考虑选择最优。

2.Bellman-Ford算法的引入

为了能够解决边上带有负权值的单源最短路问题，Bellman（贝尔曼）和Ford（福特）提出了从源点逐次途径其他顶点，以缩短达到终点的最短路径长度的问题。该算法有一个限制条件：要求图中不能包含权值总和为负值的回路。

3.适用条件与范围：

单源最短路径(从源点s到其它所有顶点v);

有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

边权可正可负(如有负权回路输出错误提示);

4.思想：

　　我们规定节点都有一个key值，key值记录的是开始节点到本节点的最小距离，每个节点也都有一个p指针指向他的前驱节点。这里我们规定一个操作叫做松弛操作，我们的算法也是最终基于这个操作的。松弛操作就是去更新key的值。

节点B的key值为8,表示从开始节点到B节点之前的最短估计距离是8，而节点A的key值3，是说从开始节点到A节点最短估计是3，当我们发现这个边时，从A到B的距离比较近，所以我们去更新B的key值，同时把B的前驱节点设置成A。这个过程就是松弛操作。

　　我们说的Bellman-Ford算法是最简单的算法，就是从开始节点开始循环每一条边，对他进行松弛操作。最后得到的路径就是最短路径。

5.算法步骤：

1.初始化：将除源点外的所有顶点的最短距离估计值 d[v] ← +∞, d[s] ←0;
2.迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）
3.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 #define MAX 0x3f3f3f3f
 5 #define N 1010
 6 int nodenum, edgenum, original; //点，边，起点
 7 typedef struct Edge //边
 8 {
 9     int u, v;
10     int cost;
11 } Edge;
12 Edge edge[N];
13 int dis[N], pre[N];
14 bool Bellman_Ford()
15 {
16     int ok;
17     for(int i = 1; i <= nodenum; ++i) //初始化，起点本身赋值为0，其余赋值为最大
18         dis[i] = (i == original ? 0 : MAX);
19     for(int i = 1; i <= nodenum - 1; ++i)
20     {
21         ok=1;
22         for(int j = 1; j <= edgenum; ++j)
23             if(dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) //松弛（顺序一定不能反）
24             {
25                 dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
26                 pre[edge[j].v] = edge[j].u;//这里用来存储路径
27                 ok=0;
28             }
29         if(ok==1) //优化这里，如果这趟没跟新任何节点就可以直接退出了。
30             break;
31     }
32     bool flag = 1; //判断是否含有负权回路
33     for(int i = 1; i <= edgenum; ++i)
34         if(dis[edge[i].v] > dis[edge[i].u] + edge[i].cost)
35         {
36             flag = 0;
37             break;
38         }
39     return flag;
40 }
41 
42 void print_path(int root) //打印最短路的路径（反向）
43 {
44     while(root != pre[root]) //前驱
45     {
46         printf("%d-->", root);
47         root = pre[root];
48     }
49     if(root == pre[root])
50         printf("%d
", root);
51 }
52 
53 int main()
54 {
55     scanf("%d%d%d", &nodenum, &edgenum, &original);//输入点边起点，一般起点规定为1
56     pre[original] = original;//为了输出最短路用的，前驱为本身
57     for(int i = 1; i <= edgenum; ++i)
58     {
59         scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);//有向图
60     }
61     if(Bellman_Ford())//如果没有负权
62         for(int i = 1; i <= nodenum; ++i) //每个点最短路
63         {
64             printf("%d
", dis[i]);
65             printf("Path:");
66             print_path(i);
67         }
68     else
69         printf("have negative circle
");
70     return 0;
71 }