算法十二：Bellman-Ford算法 - 一个点到其他所有点的最短路径（可负边）
什么是Bellman-Ford算法？Bellman-Ford算法是一种堪称完美的解决一个点到其他各点的最短路径的算法。Bellman-Ford算法的核心代码只有4行，可以解决负权边的问题。
Bellman-Ford算法的核心代码只有四行，如下
for(k=1; k<=n-1; k++)
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
dis[v[i]] = dis[u[i]] + w[i];
Bellman-Ford算法的核心代码意思是：遍历每一个点，其中每一次遍历时，遍历所有的边，对每个边进行一次松弛操作。
松弛什么？请点击查看。算法十一：Dijkstra算法 - 一个点到各个点的最短路径
现在有如下图，共5个点5条边，边都是有向边，其中点1到点2的距离为负数。如下：
为什么会进行n-1次的循环呢？因为在不包含负权回路的路径中，n个点最多有n-1条边。在负权边中，负权回路会使最短路径不断的变小，永无止境。
完整代码如下：
#include <stdio.h>
int main(){
int dis[10], i, k, m, n, u[10], v[10], w[10];
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n，边的个数m
scanf("%d %d", &n, &m);
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}
//初始化dis数组。dis数组表示源点到各个点的初始距离，初始化时都为无穷大
for(i=0; i<=n; i++){
dis[i] = maxValue;
}
//源点到源点的距离为0
dis[start] = 0;
//Bellman-Ford算法的核心语句
for(k=1; k<=n-1; k++){
for(i=1; i<=m; i++){
if(dis[v[i]] > dis[u[i]] + w[i]){
dis[v[i]] = dis[u[i]] + w[i];
}
}
}
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
return 0;
}
输入：
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//输出：
0 -3 -1 2 4
Bellman-Ford算法的时间复杂对为O(MN)。
我们可以更加完善上面的代码。比如我们已经知道了使用Bellman-Ford算法不能包含负权回路，那么我们需要检测图中是否包含负权回路:
sign = 0
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
flag = 1;
if(sign == 1)
printf("此图有负权回路");
另外，在n-1轮循环中，若n-3轮已经松弛完毕，那么n-2和n-1两次循环便毫无意义，因此增加判断，若第x轮dis数组已经不再发生变化了，则不在继续进行循环。
新版的完整代码如下：
#include <stdio.h>
int main(){
int dis[10], i, k, m, n, u[10], v[10], w[10], sign, check;
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n，边的个数m
scanf("%d %d", &n, &m);
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
}
//初始化dis数组。dis数组表示源点到各个点的初始距离，初始化时都为无穷大
for(i=0; i<=n; i++){
dis[i] = maxValue;
}
//源点到源点的距离为0
dis[start] = 0;
//Bellman-Ford算法的核心语句
for(k=1; k<=n-1; k++){
//本轮dis数组是否发生变化
ckeck = 0;
for(i=1; i<=m; i++){
if(dis[v[i]] > dis[u[i]] + w[i]){
dis[v[i]] = dis[u[i]] + w[i];
check = 1;
}
}
//本轮没有发生松弛，则不再继续进行了。
if(ckeck == 0){
break;
}
}
sign = 0
for(i=1; i<=m; i++)
if(dis[v[i]] > dis[u[i]] + w[i])
sign = 1;
if(sign == 1){
printf("此图有负权回路");
}else{
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
}
return 0;
}
在第每一轮循环中，其实只对上一次发生了松弛的边的相邻边判断是否需要松弛，因此，没有必要每次都进行m次循环（遍历所有的边判断是否需要松弛）。比如第一轮松弛了1->2和1->5，那么第二次仅仅判断2->3和5->4这两个边是否需要松弛，而不需要遍历所有的边。
在这种情况下，我们引入队列，将需要松弛的点加入队列。每个点仅仅需要入队一次即可，因为入队多次是没有意义的。初始时我们将1号点（源点）加入队列。然后开始遍历队列，对队列中每个点的边进行松弛。队列为空时所得结果便是一个点到其他所有点的最短路径。这是对上述的Bellman-Ford算法一种极大的优化。当然，在最坏的情况下，和Bellman-Ford算法的时间复杂度是一样的，即O(MN)。此优化也可以解决负权边。
完整代码如下：
#include <stdio.h>
int main(){
int dis[10] = {0}, i, j, k, m, n, u[10], v[10], w[10];
int book[10] = {0};
//first数组和next数组用来建立领接表，即first记录一个边的开头，比如第2号边的开头是点a，那么first[a]=2，a开头的下一个边是第5号边，则next[5]=a，组成一个链表的形式
int first[10], next[10];
int queue[100] = {0}, head = 1, tail = 1;
int maxValue = 9999;
//源点为1
int start = 1;
//读入点的个数n，边的个数m
scanf("%d %d", &n, &m);
//初始化dis数组。dis数组表示源点到各个点的初始距离，初始化时都为无穷大
//book用来标记那个点已经入队了，因为队列中同时出现同一个点多次是没有意义。
//first用来标记第i条边的起点
for(i=0; i<=n; i++){
dis[i] = maxValue;
book[i] = 0;
first[i] = -1;
}
//源点到源点的距离为0
dis[start] = 0;
//读入边
for(i=1; i<=m; i++){
scanf("%d %d %d", &u[i], &v[i], &w[i]);
//使用first和next两个数组建立领接表
next[i] = first[u[i]];
first[u[i]] = i;
}
//源点入队
queue[tail] = start;
tail++;
//标记已经入队的点
book[i] = start;
while(head < tail){
//当前需要处理的点，是队首的点，处理队首开头的所有边
k = first[queue[head]];
//扫描这个点开头的所有边
while( k != -1){
if(dis[v[k]] > dis[u[k]] + w[k]){
dis[v[k]] = dis[u[k]] + w[k];
if(book[v[k]] == 0){
queue[tail] = v[k];
tail++;
book[v[k]] = 1;
}
}
k = next[k];
}
//这个点开头的所有边都处理完了，就出队
book[queue[head]] = 0;
head++;
}
for(i=1; i<=n; i++){
printf("%d ", dis[i]);
}
getchar();getchar();
return 0;
}
输入：
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
//输出：
0 -3 -1 2 4
Ps:本算法参考《啊哈！算法》一书。