6.5 最短距离问题
6.5 最短距离问题
在实际中经常遇到这样的问题，从一个城市到另一个城市有若干条通路，问哪一条路的距离最短。如果用计算机解决这一问题，可用图结构描述交通网络。在网中，顶点表示城市，边的权值表示城市之间的距离，这样上述问题就变成寻找一条从一个顶点到另一个顶点所经过的路径上的各边权值之和为最小的路径，即最短路径或最短距离问题。
最短路径问题分为两种情况：一种是求从一个顶点到其他各顶点的最短路径，另一种是求每对顶点之间的最短路径。
6.5.1 单源最短距离
求单源最短路径或最短距离采用狄克斯特拉（Dijkstra）算法，该算法的思路是：设有向图G=(V,E)，其中，V={ v0,v1,…,vn-1}，cost是表示G的邻接矩阵（代价矩阵），cost[i][j]表示有向边< vi,vj >的权值。若不存在有向边< vi,vj >，则cost[i][j]的权为无穷大（∞）。设置一维数组s[0..n-1]，用于标记已找到最短路径的顶点。设顶点v为源点，集合s的初态只包含顶点v。即：
cost[i][j]=
wij 若vi≠vj且<vi,vj>?E(G)
cost[i][j]= 0 vi=vj
∞ 其他
以下用INF表示∞，通常取大于最大权值的某个数值。设置一维数组s[0..n-1]，用于标记已找到最短路径的顶点，并规定：
0 未找到源点到顶点vi的最短路径
s[i]=
1 已找到源点到顶点vi的最短路径
数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v][i]，从s之外的顶点集合V-S中选出一个顶点vu，使dist[u]的值最小。于是从源点到达vu只通过s中的顶点，把u加入集合s中调整dist中记录的从源点到V-S中每个顶点vj的距离：从原来的dist[j]和dist[u]+cost[u][j]中选择较小的值作为新的dist[j]。重复上述过程，直到s中包含其余各顶点的最短路径。
另设置一个数组path[]用于保存最短路径长度，其中，path[i]保存从源点v到终点vi当前最短路径中的前一个顶点的编号，它的初值为源点v的编号（v到vi有边时）或-1（v到vi无边时）。
对应的狄克斯特拉算法如下（n为图G的顶点数，v为源点编号）：
void Dijkstra(int cost[][MAXVEX],int n,int v)
{
int dist[MAXVEX],path[MAXVEX];
int s[MAXVEX];
int mindis,i,j,u,pre;
for(i=0;i<n;i++)
{
dist[i]=cost[v][i]; /*距离初始化*/
s[i]=0; /*s[ ]置空*/
if(cost[v][i]<INF) /*路径初始化*/
path[i]=v;
else
path[i]=-1;
}
s[v]=1;path[v]=0; /*源点编号v放入s中*/
for(i=0;i<n;i++) /*循环直到所有顶点的最短路径都求出*/
{
mindis=INF;
u=-1;
for(j=0;j<n;j++) /*选取不在s中且具有最小距离的顶点u*/
if(s[j]==0 && dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
if(u!=-1) /*找到最小距离的顶点u*/
{
s[u]=1; /*顶点u加入s中*/
for(j=0;j<n;j++) /*修改不在s中的顶点的距离*/
if(s[j]==0)
if(cost[u][j]<INF && dist[u]+cost[u][j]<dist[j])
{
dist[j]=dist[u]+cost[u][j];
path[j]=u;
}
}
}
printf("\n Dijkstra算法求解如下:\n");
for(i=0;i<n;i++) /*输出最短路径长度，路径逆序输出*/
{
if(i!=v)
{
printf(" %d->%d:",v,i);
if(s[i]==1)
{
printf("路径长度为%2d ",dist[i]);
pre=i;
printf("路径逆序为");
while(pre!=v) /*一直求解到初始顶点*/
{
printf("%d,",pre);
pre=path[pre];
}
printf("%d\n",pre);
}
else
printf("不存在路径\n");
}
}
}
如图6-24所示的有向图G7，采用狄克斯特拉求解从顶点1到其他顶点的最短路径算法过程如下。
|
|
|
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
1 |
2 |
3 |
4 |
5 |
|
{1} |
|
∞ |
0 |
15 |
50 |
10 |
∞ |
|
-1 |
0 |
1 |
1 |
1 |
-1 |
|
{2,4} |
|
∞ |
0 |
15 |
40 |
10 |
∞ |
|
-1 |
0 |
1 |
4 |
1 |
-1 |
|
{1,4,2} |
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
0 |
1 |
2 |
1 |
-1 |
|
{1,4,2,3} |
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
0 |
1 |
2 |
1 |
-1 |
|
{1,4,2,3,0} |
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
0 |
1 |
2 |
1 |
-1 |
图6-24 有向图G7
为了求解上述结果，设计如下主函数：
void main()
{
int cost[6][MAXVEX]={ /*图6-24的代价矩阵*/
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
Dijkstra(cost,6,1);
printf("\n");
}
本程序执行结果如下：
Dijkstra算法求解如下：
1->0: 路径长度为35 路径逆序为0,2,1
1->2: 路径长度为15 路径逆序为2,1
1->3: 路径长度为30 路径逆序为3,2,1
1->4: 路径长度为10 路径逆序为4,1
1->5: 不存在路径
6.5.2 每对顶点之间的最短距离
解决该问题的一种方法是：每次以一个顶点为源点，重复执行狄克斯特拉算法n次，这样便可以求得每一对顶点之间的最短路径。
另一种方法是弗洛伊德（Floyed）算法。它仍是从图的带权邻接矩阵cost出发，其基本思路是：如果从vi到vj有边，则从vi到vj存在一条长度为cost[i][j]的路径。该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(vi,v0,vj)是否存在（即判断弧(vi,v0)和(v0,vj)是否存在）。如果存在，则比较其路径长度。取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假如，在路径上再增加一个顶点v1，即如果(vi,…,v1)和(v1,…,vj)分别是当前找到的中间顶点的序号不大于0的最短路径，那么，(vi,…,v1,…,vj)就有可能是从vi到vj中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间顶点的序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进行试探。依此类推，直至经过n次比较，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点间的最短路径。
现定义一个n阶方阵序列：A-1，A0，…，Ak，…，An-1。其中：
A-1[i][j]=cost[i][j] （0≤i≤n-1,0≤j≤n-1）
Ak+1[i][j]=min{Ak[i][j]，Ak[i][k+1]+Ak[k+1][j]} （-1≤k≤n-2）
从上述计算公式可见，Ak[i][j]是从vi到vj的中间顶点的序号不大于k的最短路径的长度；An-1[i][j]就是从vi到vj的最短路径。
对应的弗洛伊德算法如下：
void Floyed(int cost[][MAXVEX],int n)
{
int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];
int i,j,k,pre;
for(i=0;i<n;i++) /*置初值*/
for(j=0;j<n;j++)
{ A[i][j]=cost[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
printf("\n Floyed算法求解如下:\n");
for(i=0;i<n;i++) /*输出最短路径*/
for(j=0;j<n;j++)
if(i!=j)
{
printf(" %d->%d:",i,j);
if(A[i][j]==INF)
{
if (i!=j)
printf("不存在路径\n");
}
else
{
printf("路径长度为:%3d ",A[i][j]);
printf("路径为%d ",i);
pre=path[i][j];
while(pre!=-1)
{
printf("%d ",pre);
pre=path[pre][j];
}
printf("%d\n",j);
}
}
}
如图6-24所示的有向图G7，采用弗洛伊德求解各顶点之间最短路径算法过程如下：
|
A（0） Path（0）： | |||||||||||||||||||||||
|
0 |
1 |
2 |
3 |
4 |
5 |
|
0 |
1 |
2 |
3 |
4 |
5 | |||||||||||
|
0 |
50 |
10 |
∞ |
∞ |
∞ |
|
-1 |
1 |
-1 |
1 |
-1 |
-1 | |||||||||||
|
∞ |
0 |
15 |
50 |
10 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
20 |
70 |
0 |
15 |
∞ |
∞ |
|
-1 |
0 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
∞ |
20 |
∞ |
0 |
35 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
30 |
0 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
3 |
∞ |
0 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
A（1） Path（1）： | |||||||||||||||||||||||
|
0 |
50 |
10 |
100 |
60 |
∞ |
|
-1 |
-1 |
-1 |
1 |
1 |
-1 | |||||||||||
|
∞ |
0 |
15 |
50 |
10 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
20 |
70 |
0 |
15 |
80 |
∞ |
|
-1 |
0 |
-1 |
-1 |
1 |
-1 | |||||||||||
|
∞ |
20 |
35 |
0 |
30 |
∞ |
|
-1 |
-1 |
1 |
-1 |
1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
30 |
0 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
3 |
∞ |
0 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
A（2） Path（2）： | |||||||||||||||||||||||
|
0 |
50 |
10 |
25 |
60 |
∞ |
|
-1 |
-1 |
-1 |
2 |
1 |
-1 | |||||||||||
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
-1 |
-1 |
2 |
-1 |
-1 | |||||||||||
|
20 |
70 |
0 |
15 |
80 |
∞ |
|
-1 |
0 |
-1 |
-1 |
1 |
-1 | |||||||||||
|
55 |
20 |
35 |
0 |
30 |
∞ |
|
2 |
-1 |
1 |
-1 |
1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
30 |
0 |
∞ |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
∞ |
∞ |
∞ |
3 |
∞ |
0 |
|
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
|
A（3） Path（3）： | |||||||||||||||||||||||
|
0 |
45 |
10 |
25 |
55 |
∞ |
|
-1 |
3 |
-1 |
2 |
3 |
-1 | |||||||||||
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
-1 |
-1 |
2 |
-1 |
-1 | |||||||||||
|
20 |
35 |
0 |
15 |
45 |
∞ |
|
-1 |
3 |
-1 |
-1 |
3 |
-1 | |||||||||||
|
55 |
20 |
35 |
0 |
30 |
∞ |
|
2 |
-1 |
1 |
-1 |
1 |
-1 | |||||||||||
|
85 |
50 |
65 |
30 |
0 |
∞ |
|
3 |
3 |
3 |
-1 |
-1 |
-1 | |||||||||||
|
58 |
23 |
38 |
3 |
33 |
0 |
|
3 |
3 |
3 |
-1 |
3 |
-1 | |||||||||||
|
A（4） Path（4）： | |||||||||||||||||||||||
|
0 |
45 |
10 |
25 |
55 |
∞ |
|
-1 |
3 |
-1 |
2 |
3 |
-1 | |||||||||||
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
-1 |
-1 |
2 |
-1 |
-1 | |||||||||||
|
20 |
35 |
0 |
15 |
45 |
∞ |
|
-1 |
3 |
-1 |
-1 |
3 |
-1 | |||||||||||
|
55 |
20 |
35 |
0 |
30 |
∞ |
|
2 |
-1 |
1 |
-1 |
1 |
-1 | |||||||||||
|
85 |
50 |
65 |
30 |
0 |
∞ |
|
3 |
3 |
3 |
-1 |
-1 |
-1 | |||||||||||
|
58 |
23 |
38 |
3 |
33 |
0 |
|
3 |
3 |
3 |
-1 |
3 |
-1 | |||||||||||
|
A（5） Path（5）： | |||||||||||||||||||||||
|
0 |
45 |
10 |
25 |
55 |
∞ |
|
-1 |
3 |
-1 |
2 |
3 |
-1 | |||||||||||
|
35 |
0 |
15 |
30 |
10 |
∞ |
|
2 |
-1 |
-1 |
2 |
-1 |
-1 | |||||||||||
|
20 |
35 |
0 |
15 |
45 |
∞ |
|
-1 |
3 |
-1 |
-1 |
3 |
-1 | |||||||||||
|
55 |
20 |
35 |
0 |
30 |
∞ |
|
2 |
-1 |
1 |
-1 |
1 |
-1 | |||||||||||
|
85 |
50 |
65 |
30 |
0 |
∞ |
|
3 |
3 |
3 |
-1 |
-1 |
-1 | |||||||||||
|
58 |
23 |
38 |
3 |
33 |
0 |
|
3 |
3 |
3 |
-1 |
3 |
-1 | |||||||||||
为了求解上述结果，设计如下主函数：
void main()
{
int cost[6][MAXVEX]={ /*图6-24的代价矩阵*/
{0,50,10,INF,INF,INF},
{INF,0,15,50,10,INF},
{20,INF,0,15,INF,INF},
{INF,20,INF,0,35,INF},
{INF,INF,INF,30,0,INF},
{INF,INF,INF,3,INF,0}};
Floyed(cost,6);
printf("\n");
}
本程序执行结果如下：
Floyed算法求解如下:
0->1:路径长度为: 45 路径为0 3 1
0->2:路径长度为: 10 路径为0 2
0->3:路径长度为: 25 路径为0 2 3
0->4:路径长度为: 55 路径为0 3 1 4
0->5:不存在路径
1->0:路径长度为: 35 路径为1 2 0
1->2:路径长度为: 15 路径为1 2
1->3:路径长度为: 30 路径为1 2 3
1->4:路径长度为: 10 路径为1 4
1->5:不存在路径
2->0:路径长度为: 20 路径为2 0
2->1:路径长度为: 35 路径为2 3 1
2->3:路径长度为: 15 路径为2 3
2->4:路径长度为: 45 路径为2 3 1 4
2->5:不存在路径
3->0:路径长度为: 55 路径为3 2 0
3->1:路径长度为: 20 路径为3 1
3->2:路径长度为: 35 路径为3 1 2
3->4:路径长度为: 30 路径为3 1 4
3->5:不存在路径
4->0:路径长度为: 85 路径为4 3 2 0
4->1:路径长度为: 50 路径为4 3 1
4->2:路径长度为: 65 路径为4 3 1 2
4->3:路径长度为: 30 路径为4 3
4->5:不存在路径
5->0:路径长度为: 58 路径为5 3 2 0
5->1:路径长度为: 23 路径为5 3 1
5->2:路径长度为: 38 路径为5 3 1 2
5->3:路径长度为: 3 路径为5 3
5->4:路径长度为: 33 路径为5 3 1 4