第七节：最短路径问题

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

dist

-1

path

-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

dist

path

-1

具体代码：

/ 邻接表存储 - 无权图的单源最短路算法 /

/ 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

dist

无穷

path

-1

当首先访问v4的时候，结果如下

下标W

dist

path

-1

然后看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

dist

path

-1

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;
}
}

不忘初心，奋力前行

数据结构【浙江大学】（第7节）整理

第七节：最短路径问题