第七节：最短路径问题
7.1 概述
最短路径问题的抽象：
在网络中，求两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。第一个顶点称为源点，最后一个顶点为终点。
问题分类：
（1）单源最短路径问题：从某固定源点触发，求其到所有其他顶点的最短路径。又分为（有无向）有权图和（有无向）无权图两种。
（2）多源最短路径问题：求任意两顶点间的最短路径。
7.2 无权图的单源最短路
按照递增（非递减）的顺序找出到各个顶点的最短路。例如图1：
图1
我们以v3作为源点，与v3距离为0的点为v3；与v3距离为1的点为v1和v6；与v3距离为2的点（也就是距离v1为1，距离v6为1）的点为v2和v4；距离v3距离为3的点（也就是距离v2为1，距离v4为1）的点为v5和v7。至此，距离各点距离v3都已经清楚。
这个算法类似于BFS算法。但是与BFS不同的是，我们不需要定义一个已经访问的变量，需要重新定义一个数组为
（1）dist[W]=S到W的最短距离。初始情况下，默认距离可以为-1、负无穷或者正无穷。
（2）dist[S]=0
（3）path[W]=S到W的路上经过的某顶点。
代码如下：
void Unweighted(Vertex S)
{
Enqueue(S,Q);
while(!IsEmpty(Q)){
V = Dequeue(Q);
for(V的每个邻接点W)
if(dist[W]==-1){
dist[W]=dist[V]+1;
path[W]=V;
Enqueue(W,Q);
}
}
}
path这个数组的作用就是记录从S到W路径中所经过的点，这个算法就是利用刚刚讲的那个每次基于前面那个点加1来得到下面一个点的这个方法。
时间复杂度为T=O(|V|+|E|)。看这个代码中while的部分，由于它都Dequeue和Enqueue了一次，所以总的次数为2V；又由于for循环遍历了V的每个邻接点W，个数为E，所以时间复杂度是O(|V|+|E|)。
7.3 无权图的单源最短路示例
这里，我们以图1中的图来做示例，仍将v3看做是源点，因此，dist和path做以下初始化：
|
下标W |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
-1 |
-1 |
0 |
-1 |
-1 |
-1 |
-1 |
|
path |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 |
调用Unweighted(3)，然后将v3入队列。然后while循环，判断队列不为空，让v3出队列给V。然后开始for循环，对于V（即v3）的每个邻接点W，如果这个点没有访问过（即该点的dist[W]==-1），则将该点的dist赋值为前一点的dist+1（刚开始的时候前一点的dist为0），然后把前一点（刚开始是v3）赋值给path的第w个值，然后把下一个点压入队列。然后把v1压出，开始for循环，对于V（即v1）的每个邻接点，再进行上面的操作，如此循环直到最后。到最后的时候，dist和path数值为：
|
下标W |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
1 |
2 |
0 |
2 |
3 |
1 |
3 |
|
path |
3 |
1 |
-1 |
1 |
2 |
3 |
4 |
具体代码：
/* 邻接表存储 - 无权图的单源最短路算法 */
/* dist[]和path[]全部初始化为-1 */
void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
{
Queue Q;
Vertex V;
PtrToAdjVNode W;
Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
dist[S] = 0; /* 初始化源点 */
AddQ (Q, S);
while( !IsEmpty(Q) ){
V = DeleteQ(Q);
for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
AddQ(Q, W->AdjV);
}
} /* while结束*/
}
7.4 有权图的单源最短路
仍然是按照递增的顺序找出到各个顶点的最短路。解决这个问题的经典算法就是：Dijkstra算法。
（1）Dijkstra算法
①令S={源点s+已经确定了最短路径的顶点vi}
②对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过S中的顶点，即路径{s->(vi∈S)->v}的最小长度。
若路径是按照递增（非递减）的顺序生成的，则：
真正的最短路径必须只经过s中的顶点；
每次从未收录的顶点中选一个dist最小的收录（贪心算法）
增加一个v进入S，可能影响另外一个w的dist值（若使w的dist值缩小，则v必定在s到w的路径上，并且v到w有一条边），dist[w]=min{dist[w],dist[v]+<v,w>的权重}。代码如下：
void Dijkstra(Vertex s)
{
while(1){
V=未收录顶点中dist最小者;
if(这样的V不存在)
break;
collected[V] = true;
for(V的每个邻接点W）
if(collected[W] == false)
if(dist[V]+E<k,w> < dist[W])
{
dist[W] = dist[V] +E<v,w>;
path[W] =V;
}
}
}
注意：该算法不能解决有负边的情况。
若只看这段伪码，我们无法判断其复杂度，这主要是因为未收录顶点中dist最小者的这个算法的复杂度我们无法判断。这个算法有以下几种：
①直接扫描所有未收录顶点-O(|V|)，则T=O(|V|2+|E|)。对稠密图效果好。
②将dist存在最小堆中-O(log|V|)。更新dist[w]的值-O(log|V|)。总体复杂度为T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)。对稀疏图效果好。
7.5 有权图的单源最短路示例
图如图2所示。
图2
这里我们以v1位源点。dist和path初始化结果如下所示：
|
下标W |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
2 |
无穷 |
1 |
无穷 |
无穷 |
无穷 |
|
path |
-1 |
1 |
-1 |
1 |
-1 |
-1 |
-1 |
当首先访问v4的时候，结果如下
|
下标W |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
2 |
3 |
1 |
3 |
9 |
5 |
|
path |
-1 |
1 |
4 |
1 |
4 |
4 |
4 |
然后看v2，由于v4已经访问过了，因此接下来看v5，由于到v5的距离为12，大于前面的距离，因此跳出循环。由于v2的邻接点只有v4和和v5，因此跳出v2。
接下来看v3和v5距离一样，那么就先看v3。v3的邻接点有v1和v6，v1已经被访问过，所以无视，直接看v6，此时可以看出v3到v6距离为5，所以总距离为8，小于原来的9。因此更新dis[6]=9，path[6]=3。然后看v5，v5只有一个邻接点，就是v7，这样经过v5到v7的距离为9，大于原来的距离，不更新。
在v6和v7中，v7的距离更短一点，所以先看v7。v7的邻接点只有v6。若经过v7访问v6的距离为6，小于原来的8，更新dis[6]=6，path[6]=7。
由于v6没有任何邻接点，所以v6直接不做判断。最后更新的结果如下：
|
下标W |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
dist |
0 |
2 |
3 |
1 |
3 |
6 |
5 |
|
path |
-1 |
1 |
4 |
1 |
4 |
7 |
4 |
7.6 多源最短路算法
方法1：直接将单源最短路算法调用|V|遍，T=O(|V|3+|E|×|V|)，适合稀疏图。
方法2：Floyd算法，复杂度T=O(|V|3)，更适合稠密图。
（1）Floyd算法
①Dk[i][j]=路径{i->{l<=k}->j}的最小长度。
②D0,D1,…,D[V]-1[i][j]即给出了i到j的真正最短距离。
③最初的D-1是带权的邻接矩阵，对角元素是0。
④若i和j之间没有直接的边，D[i][j]定义为正无穷。
⑤当Dk-1已经完成，递推到Dk时：
或者k∉最短路径{i->{l<=k}->j}，则Dk=Dk-1；
或者k∈{i->{l<=k}->j}，则该路径必定由两段最短距离组成：Dk [i][j]= Dk-1[i][k]+ Dk-1[k][j]。
源代码为：
void Floyd()
{
for(i=0;i<N;i++)
for(j=0lj<N;j++){
D[i][j]=G[i][j];
path[i][j]=-1;
}
for(k=0;k<N;k++)
for(i=0;i<N;i++)
if(D[i][k]+D[k][j]<D[i][j])
{
D[i][j]=D[i][k]+D[k][j];
path[i][j]=k;
}
}
文章评论