博客为参考《啊哈！算法》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.只有五行的算法——Floyd-Warshall
有些城市之间有公路，有些城市之间则没有。求任意两个城市之间的最短路径。
上图中有4个城市8条公路，公路上的数字表示这条公路的长短。这些公路是单向的。这个问题也被称为“多源最短路径”问题。
我们用一个4*4的矩阵来存储地图（二维数组e）：
我们可以通过深度或广度优先搜索求出两点之间的最短路径。所以进行$n^2$遍深度或广度优先搜索，即对每两个点都进行一次深度或广度优先搜索，便可以求得任意两点之间的最短路径。
当任意两点之间不允许经过第三个点时，这些城市之间的最短路程就是初始路程，如下。
假如现在只允许经过1号顶点，求任意两点之间的最短路程，应该如何求呢？只需判断e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是从i号顶点到j号顶点之间的路程。代码实现如下：
1
2
3
4
5
6
7
8
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(e[i][j] > e[i][1]+e[1][j])
e[i][j] = e[i][1]+e[1][j];
}
}
在只允许经过1号顶点的情况下，任意两点之间的最短路程更新为：
接下来继续求只允许经过1和2号两个顶点的情况下任意两点之间的最短路程。如何做呢？我们需要在只允许经过1号顶点时任意两点的最短路程的结果下，再判断如果经过2号顶点是否可以使得i号顶点到j号顶点之间的路程变得更短，即判断e[i][2]+e[2][j]是否比e[i][j]要小。代码实现为如下。
1
2
3
4
5
6
7
8
9
10
11
//经过1号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j] > e[i][1]+e[1][j])
e[i][j]=e[i][1]+e[1][j];
//经过2号顶点
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j] > e[i][2]+e[2][j])
e[i][j]=e[i][2]+e[2][j];
在只允许经过1和2号顶点的情况下，任意两点之间的最短路程更新为：
同理，继续在只允许经过1、2和3号顶点进行中转的情况下，求任意两点之间的最短路程。任意两点之间的最短路程更新为：
最后允许通过所有顶点作为中转，任意两点之间最终的最短路程为：
整个算法过程虽然说起来很麻烦，但是代码实现却非常简单，核心代码只有五行：
1
2
3
4
5
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j] > e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
这是一种“动态规划”的思想。下面给出这个算法的完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf=99999999; //用inf存储一个我们认为的正无穷值
//读取n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3; //表示顶点t1到顶点t2的路程是t3
}
//Floyd-Warshall算法核心语句
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j] > e[i][k]+e[k][j])
e[i][j] = e[i][k]+e[k][j];
//输出最终的结果
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%10d",e[i][j]);
}
printf("\n");
}
return 0;
}
上面代码的输入数据样式为：
1
2
3
4
5
6
7
8
9
4 8
1 2 2
1 3 6
1 4 4
2 3 3
3 1 7
3 4 1
4 1 5
4 3 12
得到最终结果如下：
该方法的时间复杂度是$O(N^3)$。另外需要注意的是，Floyd-Warshall算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路径。例如下面这个图就不存在1号顶点到3号顶点的最短路径，因为1->2->3->1->2->3->…1->2->3这样路径中，每绕一次1->2->3这样的环，最短路径就会减少1，永远找不到最短路径。其实如果一个图中带有“负权回路”，那么这个图则没有最短路径。
2.Dijkstra算法——通过边实现松弛
本节来学习指定一个点（源点）到其余各个顶点的最短路径，也叫做“单源最短路径”。例如求下图中的1号顶点到2、3、4、5、6号顶点的最短路径。
仍然使用二维数组e来存储顶点之间边的关系，初始值如下。
我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程，如下。
我们将此时dis数组中的值称为最短路程的“估计值”。
既然是求1号顶点到其余各个顶点的最短路程，那就先找一个离1号顶点最近的顶点。通过数组dis可知当前离1号顶点最近的是2号顶点。当选择了2号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”，即1号顶点到2号顶点的最短路程就是当前dis[2]值。因为目前离1号顶点最近的是2号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得1号顶点到2号顶点的路程进一步缩短了。因为1号顶点到其他顶点的路程肯定没有1号到2号顶点短。
既然选了2号顶点，接下来再来看2号顶点有哪些出边呢。有2->3和2->4这两条边。先讨论通过2->3这条边能否让1号顶点到3号顶点的路程变短，也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。
我们发现dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此，dis[3]要更新为10。这个过程有个专业术语叫做“松弛”。这便是Dijkstra算法的主要思想。
同理，通过2->4（e[2][4]），可以将dis[4]的值从$\infty$松弛为4（dis[4]初始为$\infty$，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此dis[4]要更新为4）。
刚才我们对2号顶点所有的出边进行了松弛。松弛完毕之后dis数组为：
接下来，继续在剩下的3、4、5和6号顶点中，选出离1号顶点最近的顶点。通过上面更新过的dis数组，当前离1号顶点最近的是4号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对4号顶点的所有出边（4->3，4->5和4->6）用刚才的方法进行松弛。松弛完毕之后dis数组为：
继续在剩下的3、5和6号顶点中，选出离1号顶点最近的顶点，这次选择3号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对3号顶点的所有出边（3->5）进行松弛。松弛完毕之后dis数组为：
继续在剩下的5和6号顶点中，选出离1号顶点最近的顶点，这次选择5号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后dis数组为：
最后对6号顶点的所有出边进行松弛。因为这个例子中6号顶点没有出边，因此不用处理。到此，dis数组中所有的值都已经从“估计值”变为了“确定值”。
最终dis数组如下，这便是1号顶点到其余各个顶点的最短路径。
完整的Dijkstra算法代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <stdio.h>
int main()
{
int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
int inf=99999999; //用inf存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j)
e[i][j]=0;
else
e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i=1;i<=n;i++)
dis[i]=e[1][i];
//book数组初始化
for(i=1;i<=n;i++)
book[i]=0;
book[1]=1;
//Dijkstra算法核心语句
for(i=1;i<=n-1;i++)
{
//找到离1号顶点最近的顶点
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0 && dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(v=1;v<=n;v++)
{
if(e[u][v]<inf)
{
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
//输出最终的结果
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
getchar();
getchar();
return 0;
}
可以输入以下数据进行验证。
1
2
3
4
5
6
7
8
9
10
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
运行结果是：
1
0 1 8 4 13 17
通过上面的代码我们可以看出，这个算法的时间复杂度是$O(N^2)$。其中每次找到离1号顶点最近的顶点的时间复杂度是$O(N)$，这里我们可以用“堆”（后续博文会有介绍）来优化，使得这一部分的时间复杂度降低到$O(\log N)$。另外对于边数$M$少于$N^2$的稀疏图来说（我们把$M$远小于$N^2$的图称为稀疏图，而$M$相对较大的图称为稠密图），我们可以用邻接表来代替邻接矩阵，使得整个时间复杂度优化到$O(M+N)\log N$。请注意！在最坏的情况下$M$就是$N^2$，这样的话$(M + N) \log N$要比$N^2$还要大。但是大多数情况下并不会有那么多边，因此$(M + N) \log N$要比$N^2$小很多。
这里我们主要来讲解如何使用邻接表来存储一个图，先上数据。
1
2
3
4
5
6
4 5
1 4 9
2 4 6
1 2 5
4 3 8
1 3 7
现在用邻接表来存储这个图，先给出代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n,m,i;
//u,v和w的数组大小要根据实际情况来设置，要比m的最大值要大1
int u[6],v[6],w[6];
//first和next的数组大小要根据实际情况来设置，要比n的最大值要大1
int first[5],next[5];
scanf("%d %d",&n,&m);
//初始化first数组下标1~n的值为-1，表示1~n顶点暂时都没有边
for(i=1;i<=n;i++)
first[i]=-1;
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&u[i],&v[i],&w[i]); //读入每一条边
//下面两句是关键
next[i]=first[u[i]];
first[u[i]]=i;
}
这里介绍的是使用数组来实现邻接表，而没有使用真正的指针链表。这种方法为每个顶点i（i从1~n）都设置了一个链表，里面保存了从顶点i出发的所有的边（这里用first和next数组来实现）。首先我们需要为每一条边进行1~m的编号。用u、v和w三个数组来记录每条边的信息，即u[i]、v[i]和w[i]表示第i条边是从第u[i]号顶点到v[i]号顶点（u[i]->v[i]），且权值为w[i]。first数组的1~n号单元格分别用来存储1~n号顶点的第一条边的编号，初始的时候因为没有边加入所以都是-1。即first[u[i]]保存顶点u[i]的第一条边的编号，next[i]存储“编号为i的边”的“下一条边”的编号。
那么如何遍历1号顶点的每一条边呢？请看下图：
遍历每个顶点的边，其代码如下。
1
2
3
4
5
6
7
8
9
for(i=1;i<=n;i++)
{
k=first[1];
while(k!=-1)
{
printf("%d %d %d\n", u[k], v[k], w[k]);
k=next[k];
}
}
可以发现使用邻接表来存储图的时间空间复杂度是$O(M)$，遍历每一条边的时间复杂度也是$O(M)$。如果一个图是稀疏图的话，$M$要远小于$N^2$。因此稀疏图选用邻接表来存储要比用邻接矩阵来存储好很多。
最后，本节介绍的求最短路径的算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用本算法求最短路径的图是不能有负权边的，因为扩展到负权边的时候会产生更短的路程，有可能就破坏了已经更新的点路程不会改变的性质。既然用这个算法求最短路径的图不能有负权边，那有没有可以求带有负权边的指定顶点到其余各个顶点的最短路径算法呢？请看下一节。
3.Bellman-Ford——解决负权边
Dijkstra算法虽然好，但是它不能解决带有负权边（边的权值为负数）的图。本节要介绍一个无论是思想上还是代码实现上都堪称完美的最短路算法：Bellman-Ford。其核心代码只有4行：
1
2
3
4
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];
上面的代码中，外循环一共循环了n-1次（n为顶点的个数），内循环循环了m次（m为边的个数），即枚举每一条边。dis数组的作用与Dijkstra算法一样，是用来记录源点到其余各个顶点的最短路径。u、v和w三个数组是用来记录边的信息。例如第i条边存储在u[i]、v[i]和w[i]中，表示从顶点u[i]到顶点v[i]这条边（u[i]->v[i]）权值为w[i]。
1
2
if(dis[v[i]] > dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]]+w[i];
上面这两行代码的意思是：看看能否通过u[i]->v[i]（权值为w[i]）这条边，使得1号顶点到v[i]号顶点的距离变短。即1号顶点到u[i]号顶点的距离（dis[u[i]]）加上u[i]->v[i]这条边（权值为w[i]）的值是否会比原先1号顶点到v[i]号顶点的距离（dis[v[i]]）要小。这一点其实与Dijkstra的“松弛”操作是一样的。现在我们要把所有的边都松弛一遍，代码如下。
1
2
3
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]]+w[i];
那把每一条边都“松弛”一遍后，究竟会有什么效果呢？现在来举个具体的例子。求下图1号顶点到其余所有顶点的最短路径。
我们还是用一个dis数组来存储1号顶点到所有顶点的距离。
上方右图中每个顶点旁的值（带下划线的数字）为该顶点的最短路“估计值”（当前1号顶点到该顶点的距离），即数组dis中对应的值。根据边给出的顺序，先来处理第1条边“2 3 2”，即判断dis[3]是否大于dis[2]+2。此时dis[3]是$\infty$，dis[2]是$\infty$，因此dis[2]+2也是$\infty$，所以通过“2 3 2”这条边不能使dis[3]的值变小，松弛失败。
同理，继续处理第2条边“1 2 -3”，我们发现dis[2]大于dis[1]+(-3)，通过这条边可以使dis[2]的值从$\infty$变为-3，因此松弛成功。用同样的方法处理剩下的每一条边。对所有的边松弛一遍后的结果如下。
我们发现，在对每条边都进行一次松弛后，已经使得dis[2]和dis[5]的值变小，即1号顶点到2号顶点的距离和1号顶点到5号顶点的距离都变短了。
接下来我们需要对所有的边再进行一轮松弛，操作过程与上一轮一样，再来看看又会发生什么变化。
这一轮松弛时，我们发现，现在通过“2 3 2”这条边，可以使1号顶点到3号顶点的距离（dis[3]）变短了。但这条边为什么在上一轮松弛失败了，这一轮却成功了呢？因为在第一轮松弛过后，1号顶点到2号顶点的距离（dis[2]）已经发生了变化，这一轮再通过“2 3 2”这条边进行松弛的时候，已经可以使1号顶点到3号顶点的距离（dis[3]）的值变小。
换句话说，第1轮在对所有的边进行松弛之后，得到的是从1号顶点“只能经过一条边”到达其余各顶点的最短路径长度。第2轮在对所有的边进行松弛之后，得到的是从1号顶点“最多经过两条边”到达其余各顶点的最短路径长度。如果进行k轮的话，得到的就是1号顶点“最多经过k条边”到达其余各顶点的最短路径长度。现在又有一个新问题：需要进行多少轮呢？
只需要进行n-1轮就可以了。因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1个边。
那真的最多只能包含n-1条边？最短路径中不可能包含回路吗？
答案是：不可能！最短路径肯定是一个不包含回路的简单路径。回路分为正权回路（即回路权值之和为正）和负权回路（即回路权值之和为负）。我们分别来讨论一下为什么这两种回路都不可能有。如果最短路径中包含正权回路，那么去掉这个回路，一定可以得到更短的路径。如果最短路径中包含负权回路，那么肯定没有最短路径，因为每多走一次负权回路就可以得到更短的路径。因此，最短路径肯定是一个不包含回路的简单路径，即最多包含n-1条边，所以进行n-1轮松弛就可以了。
回到之前的例子，继续进行第3轮和第4轮松弛操作，这里只需进行4轮就可以了，因为这个图一共只有5个顶点。
这个例子其实都不用松弛到第4轮就可以结束了，n-1轮只是最多的情况下。
Bellman-Ford算法的完整代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
int main()
{
int dis[10],i,k,n,m,u[10],v[10],w[10];
int inf = 99999999; //用inf存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//读入边
for(i=1;i<=m;i++)
scanf("%d %d %d",&u[i],&v[i],&w[i]);
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i=1;i<=n;i++)
dis[i]=inf;
dis[1]=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]);
getchar();getchar();
return 0;
}
输入以下数据进行验证。
1
2
3
4
5
6
5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3
运行结果是：
1
0 -3 -1 2 4
显然，Bellman-Ford算法的时间复杂度是$O(NM)$，这个时间复杂度貌似比Dijkstra算法还要高，我们还可以对其进行优化。在实际操作中，Bellman-Ford算法经常会在未达到n-1轮松弛前就已经计算出最短路，之前我们已经说过，n-1其实是最大值。因此可以添加一个一维数组用来备份数组dis。如果在新一轮的松弛中数组dis没有发生变化，则可以提前跳出循环，代码如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
int main()
{
int dis[10],bak[10],i,k,n,m,u[10],v[10],w[10],check,flag;
int inf = 99999999; //用inf存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//读入边
for(i=1;i<=m;i++)
scanf("%d %d %d",&u[i],&v[i],&w[i]);
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i=1;i<=n;i++)
dis[i]=inf;
dis[1]=0;
//Bellman-Ford算法核心语句
for(k=1;k<=n-1;k++)
{
//将dis数组备份至bak数组中
for(i=1;i<=n;i++)
bak[i]=dis[i];
//进行一轮松弛
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]]+w[i])
dis[v[i]] = dis[u[i]] + w[i];
//松弛完毕后检测dis数组是否有更新
check=0;
for(i=1;i<=n;i++)
{
if(bak[i] != dis[i])
{
check=1;
break;
}
}
//如果dis数组没有更新，提前退出循环结束算法
if(check==0)
break;
}
//检测负权回路
flag=0;
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]]+w[i])
flag=1;
if(flag==1)
printf("此图含有负权回路");
else
{
//输出最终的结果
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
}
getchar();getchar();
return 0;
}
该算法有时也被称为Bellman-Ford-Moore算法。
4.Bellman-Ford的队列优化
Bellman-Ford算法在每实施一次松弛操作后，就会有一些顶点已经求得其最短路，此后这些顶点的最短路的估计值就会一直保持不变，不再受后续松弛操作的影响，但是每次还要判断是否需要松弛，这里浪费了时间。因此，Bellman-Ford算法的另一种优化：每次仅对最短路程发生变化了的点的相邻边执行松弛操作。我们用队列来实现，算法大致如下。
每次选取队首顶点u，对顶点u的所有出边进行松弛操作。例如有一条u->v的边，如果通过u->v这条边使得源点到顶点v的最短路程变短（dis[u]+e[u][v]<dis[v]），且顶点v不在当前的队列中，就将顶点v放入队尾。需要注意的是，同一个顶点同时在队列中出现多次是毫无意义的，所以我们需要一个数组来判重（判断哪些点已经在队列中）。在对顶点u的所有出边松弛完毕后，就将顶点v出队。接下来不断从队列中取出新的队首顶点再进行如上操作，直至队列空为止。
下面我们用一个具体的例子来详细讲解。
我们用数组dis来存放1号顶点到其余各个顶点的最短路径。初始时dis[1]为0，其余为无穷大。接下来将1号顶点入队。队列这里用一个数组que以及两个分别指向队列头和尾的变量head和tail来实现。
先来看当前队首1号顶点的边1->2，看通过1->2能否让1号顶点到2号顶点的路程（即dis[2]）变短，也就是说先来比较dis[2]和dis[1]+(1->2)的大小。dis[2]原来的值为$\infty$，dis[1]+(1->2)的值为2，因此松弛成功，dis[2]的值从$\infty$更新为2。并且当前2号顶点不在队列中，因此将2号顶点入队。
同样，对1号顶点剩余的出边进行如上操作，处理完毕后数组dis和队列que状态如下：
对1号顶点处理完毕后，就将1号顶点出队（head++即可），再对新队首2号顶点进行如上处理。在处理2->5这条边时需要特别注意一下，2->5这条边虽然可以让1号顶点到5号顶点的路程变短（dis[5]的值从10更新为9），但是5号顶点已经在队列中了，因此5号顶点不能再次入队。对2号顶点处理完毕后数组dis和队列que状态如下：
在对2号顶点处理完毕后，需要将2号顶点出队，并依次对剩下的顶点做相同的处理，直到队列为空为止。最终数组dis和队列que状态如下：
下面是代码实现，我们还是用邻接表来存储这个图，具体如下。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
int main()
{
int n,m,i,j,k;
//u,v和w的数组大小要根据实际情况来设置，要比m的最大值要大1
int u[8],v[8],w[8];
//first要比n的最大值要大1,next要比m的最大值要大1
int first[6],next[8];
int dis[6]={0},book[6]={0};//book数组用来记录哪些顶点已经在队列中
int que[101]={0},head=1,tail=1;//定义一个队列,并初始化队列
int inf=99999999;//用inf存储一个我们认为的正无穷值
//读入n和m,n表示顶点个数,m表示边的条数
scanf("%d %d",&n,&m);
//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程
for(i=1;i<=n;i++)
dis[i]=inf;
dis[1]=0;
//初始化book数组,初始化为0,刚开始都不在队列中
for(i=1;i<=n;i++)
book[i]=0;
//初始化first数组下标1~n的值为-1,表示1~n顶点暂时都没有边
for(i=1;i<=n;i++)
first[i]=-1;
for(i=1;i<=m;i++)
{
//读入每一条边
scanf("%d %d %d",&u[i],&v[i],&w[i]);
//下面两句是建立邻接表的关键
next[i]=first[u[i]];
first[u[i]]=i;
}
//1号顶点入队
que[tail]=1;
tail++;
book[1]=1;//标记1号顶点已经入队
while(head<tail)//队列不为空的时候循环
{
k=first[que[head]];//当前需要处理的队首顶点
while(k!=-1)//扫描当前顶点所有的边
{
if(dis[v[k]] > dis[u[k]]+w[k])//判断是否松弛成功
{
dis[v[k]]=dis[u[k]]+w[k];//更新顶点1到顶点v[k]的路程
//这的book数组用来判断顶点v[k]是否在队列中
//如果不使用一个数组来标记的话,判断一个顶点是否在队列中每次都需要从队列的head到tail扫一遍,很浪费时间
if(book[v[k]]==0)//0表示不在队列中,将顶点v[k]加入队列中
{
//下面两句是入队操作
que[tail]=v[k];
tail++;
book[v[k]]=1;//同时标记顶点v[k]已经入队
}
}
k=next[k];
}
//出队
book[que[head]]=0;
head++;
}
//输出1号顶点到其余各个顶点的最短路径
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
getchar();getchar();
return 0;
}
可以输入以下数据进行验证。
1
2
3
4
5
6
7
8
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
运行结果是：
1
0 2 5 9 9
使用队列优化的Bellman-Ford算法在形式上和广度优先搜索非常类似，不同的是在广度优先搜索的时候一个顶点出队后通常就不会再重新进入队列。而这里一个顶点很可能在出队列之后再次被放入队列，也就是当一个顶点的最短路程估计值变小后，需要对其所有出边进行松弛，但是如果这个顶点的最短路程估计值再次变小，仍需要对其所有出边再次进行松弛，这样才能保证相邻顶点的最短路程估计值同步更新。需要特别说明一下的是，使用队列优化的Bellman-Ford算法的时间复杂度在最坏情况下也是$O(NM)$。通过队列优化的Bellman-Ford算法如何判断一个图是否有负环呢？如果某个点进入队列的次数超过n次，那么这个图则肯定存在负环。
5.最短路径算法对比分析
