第六章
Floyd-Warshall算法
只有五行核心的算法
简介
假设我们有四个点。每个点之间都有一定的距离，或者甚至没有路
现在我们想要知道如何获得两点之间的最短路径
使用之前说的深度优先或者宽度优先当然是可以的，不过有没有更好的办法？
于是我们使用了Floyd-Warshall，先进了一些的算法
算法核心
首先我们要知道，有的时候，通过n个点而从A->B，是有可能比直达得到更短的路径
基于这个思路，我们逐步推进
1.首先是直达，这个就不用说了
2.然后我们假设“如果允许在点1中转”，得到新的结果比较，更新数据
3.慢慢来，随后假设“如果允许在点1和点2中转”，再次更新数据
4.遍历所有可能，得到最终结果
实现
具体怎么实现呢，我们先做一波基础操作
首先首先，我们同样用一个二维数组e来存储路径情况(其实就是图的信息)
然后是比较，以顶点1为例，可以写成：
1
2
3
4
5
6
7
8
9
10
11
12
13
| for(i=1;i<=n,i++)
{
for(j=1;j<=n;j++)
{
if(i[e][j] > e[1][j]+e[1][j]){
e[i][j] = e[i][1]+e[1][j]
}
}
}
|
点2，点3，点4…都是同理，于是我们使用一个循环解决这件事情：
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];
|
简单粗暴的五行，包含了Floyd-Warshall算法的思想
一句话概括，Floyd-Warshall算法就是：
从i号顶点到j号顶点，只经过前k号点时，其最短路径
通过不断推进，我们最终可以得到从i到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
42
| #include <stdio.h>
int main()
{
int e[10][10],k,i,j,n,m,t1,t2,t3;
int inf = 99999999 ;
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 ;
}
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 ;
}
|
其实把9999999定义成正无穷还是挺乱挺麻烦的，而且天知道会不会有bug
于是我们还可以增加一些判断条件来改善一下情况
1
2
3
4
5
6
|
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][k]<inf && e[k][j]<inf && e[i][j] > e[i][k]+e[k][j])
e[i][j] = e[i][k]+e[k][j];
|
另外…
Floyd-Warshall算法可以处理带有负权边的图
但是没办法处理带有“负权回路”(也叫”负权环”)的图
Dijkstra算法——单源最短路径
Dijkstra算法是用来处理”指定一个点，计算该点到其余各个顶点的最短路径”这件事
简介
和上文有点像，因为当我们讨论一点到各个点的距离的时候，我们就不得不计算各种中转站
我们这里得到了一个新定义，松弛，我们认为它是：
如果两点距离通过中转点缩短了距离，我们就把这个过程叫松弛
Dijkstra算法实际就是 “选点，松弛，更新，选点” 的不断循环，直到得到结果
核心
我们这里使用两个数组
二维数组e来存储两点之间的路径关系
一维数组dis来存储一个点到其余各个点的初始路程(接下来会以1当例子)
我们暂且把dis中的值叫做“估计值”
我们先选择离1最近的点，得到其距离，和“估计值”比较，得到“确定值”
比如由1得到2，再由2得到其它边
然后更新、比较数据
步骤
1.将所有顶点分为两个部分。已知最短路径的集合P，未知的集合Q。
最开始P中只有源点一个顶点。我们可以用book数组来标记已知点
2.设置源点到自己的路径为0.
如果存在源点能直接到达的顶点i,则设置dis[i]为e[s][i]
把不能直接到达的顶点，设dis[i]为正无穷
3.在集合Q中选择一个离源点最近的顶点u(dis[u]最小)加入到P
检查所有以u为起点的边，每一条边都进行一次松弛的检查
边长为dis[u]+e[u][v]，比较这个值和dis[u]的大小
4.重复第三步，直到Q为空，算法结束
代码示例
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
| #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 ;
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<=n;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
for(i=1;i=n;i++)
dis[i] = e[1][i];
for(i=1;i<n;i++)
book[i] = 0 ;
book[1]=1;
for(i=1;i<=n-1;i++)
{
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();gerchar();
return 0 ;
}
|
事实上，这是一种基于贪心策略的算法
邻接表
我们可以利用邻接表来存储一个图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int n,m,i ;
int u[6],v[6],w[6] ;
int first[5],next[6];
scanf("%d %d",&n,&m);
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 ;
}
|
用u,v,w三个数组来记录每条边的信息，即u[i],v[i],w[i]表示:
第i条边是从第u[i]号顶点到第v[i]顶点(u[i]->v[i]),且权值为w[i]
next[i]存储”编号为i的边”的”下一条边”的编号
Bellman-Ford算法
很强的一个算法，无论是思路、思想、代码实现都很优秀
而且，它可以解决负权边的问题
简介
一句话概括这个算法就是：“对所有的边进行n-1次松弛操作”
一样的，我们用uvw三者表示“从顶点u[i]到顶点v[i]的这条边，权值为w[i]”
随后检查，新的距离会不会比原本的距离短
1.用dis数组初始化估计值，并且把除了起始点之外的，都设置为正无穷大(解释见后)
2.按边的图的数组中的顺序，遍历检查”这条路会不会距离变短”
3.由于起始点到自身的距离是0，所以一定存在它到相邻区域的更小值，于是更新
比如到2的预设值是正无穷，而有一条(u=1,v=2,w=-3)的路，那么这个正无穷就会被更新为-3
4.重复2-3步，不断得到新的结果
5.返回最终结果
我们实验发现，可以知道“在第一轮后，实际上得到的是’从一号顶点，只经过一条边，到其余点的最短路径’”
而实际2-3的重复，就是利用“一次次的松弛”，达到对条件 “只经过k条边”的递增
最终，只需要进行n-1轮，就可以了。再包含n个顶点的图中，两点之间的最短路径最多包含n-1个边
(而且不含回路：正回路的距离会越来越远，负回路不可能有最短路径，因为它会一直一直递减)
实现
Bellman-Ford算法的核心四行代码如下，体现了我们上文所说的操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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是点个数，m是边个数
Bellman-Ford算法还可以检测负权回路，如果在n-1次松弛后，最短路径还在变化，那就是有负权回路了
具体代码实现如下：
```C
flag = 0 ;
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]] + w[i])
flag = 1 ;
if(flag == 1)
printf("此图包含负权回路") ;
|
代码示例
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <stdio.h>
int main()
{
int dis[10],bal[10],i,k,n,m,u[10],v[10],w[10],check,flag ;
int inf = 99999999 ;
scanf("%d %d",&n,&m);
for(i = 1 ; i< m ; i++){
scanf("%d %d %d",&u[i],&v[i],&w[i]);s
}
for(i=1;i<=n;i++)
dis[i] = inf ;
dis[1] = 0 ;
for(k=1;k<=n-1;k++)
{
check = 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 ;
}
}
}
flag = 0 ;
for(i=1;i<=m;i++)
if(dis[v[i]] > dis[u[i]] + w[i])
flag = 1 ;
if(flag == 1)
print("此图存在负权回路");
else{
for(i=1;i<=n;i++)
printf("%d" , dis[i]);
}
getchar();getchar();
return 0 ;
}
|
Bellman-Ford优化
我们知道，在最开始的算法中，我们每一次操作后就会进行一次松弛的判断
实际上，这浪费了我们的时间：每次操作后有些顶点的最短路就不会变化了
实际上我们可以这样做：每次仅仅对最短路的估计值发生了变化的顶点的所有出边执行松弛操作
实操
我们可以利用队列来维护这些点
我们每次都选取队首的顶点u，对顶点u的所有出边进行松弛操作
如果通过u->v这条边，可以使得源点到顶点v的最短路径变短，且顶点v不在当前队列中
那么我们就把顶点v放入队尾
在对顶点u的所有出边松弛完成之后，就将u出队
实际上，我们就是在完成“得到队首，更新判断队首，出队进行下一轮”的操作
优化代码
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
73
74
75
| #include <stdio.h>
int main()
{
int n,m,i,j,k ;
int u[8],v[8],w[8];
int first[6],next[8] ;
int dis[6]={0},book[6]={0} ;
int que[101] = {0} , head = 1 , tail = 1 ;
int inf = 99999999 ;
scanf("%d %d",&n,&m) ;
for(i=1;i<=n;i++)
dis[i] = inf ;
dis[1] = 0 ;
for(i=1;i<=n;i++)
book[i] = 0 ;
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 ;
}
que[tail] = 1 ;
tail++;
book[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] ;
if(book[v[k]] == 0){
que[tail] = v[k] ;
tail++;
book[v[k]] = 1 ;
}
}
k = next[k];
}
book[que[head]] = 0 ;
head++;
}
for(i=1;i<=n;i++)
printf("%d",dis[i]);
getchar();getchar();
return 0 ;
}
|
其关键之处在于：只有那些在前一遍松弛中改变了最短路程估计值的顶点，才可能引起它们邻接点最短路径估计值发生改变
另外，这种优化在形式上和宽度优先搜索类似，不过宽度优先中出队的元素不会返回队列，而这里要看情况而定
