第七节:最短路径问题

7.1 概述

最短路径问题的抽象:

在网络中,求两个不同顶点之间的所有路径中,边的权值之和最小的那一条路径。这条路径就是两点之间的最短路径。第一个顶点称为源点,最后一个顶点为终点

问题分类:

(1)单源最短路径问题:从某固定源点触发,求其到所有其他顶点的最短路径。又分为(有无向)有权图和(有无向)无权图两种。

(2)多源最短路径问题:求任意两顶点间的最短路径。

7.2 无权图的单源最短路

按照递增(非递减)的顺序找出到各个顶点的最短路。例如图1:

 1.jpg

图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的路上经过的某顶点。

代码如下:

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

具体代码:

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>的权重}。代码如下:

注意:该算法不能解决有负边的情况。

若只看这段伪码,我们无法判断其复杂度,这主要是因为未收录顶点中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.jpg 

图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]。

源代码为: