第七节:最短路径问题

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

代码如下:

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

源代码为:

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