第7章 图结构

int v; cout<<\建立一个有向网的邻接矩阵G:\\n\ CreateGraph_MG(G,gk); cout<<\有向网G的邻接矩阵为:\\n\ DisplyMG(G); cout<<\输入源点下标:\ ShortestPath_DIJ(dist,G,v); cout<<\源点为:v=\到各点的最短路径为:\\n\ Disply_Dist(dist); }程序运行演示结果为：

建立一个有向网的邻接矩阵G:

输入顶点数vexnum和弧数arcnum:7 12↙ 按某种顺序输入7个顶点的值: 1 2 3 4 5 6 7↙ 输入图中12条边(弧)和权的信息u v w:

1 2 2 1 4 1 2 4 3 2 5 10 3 1 4 3 6 5 4 3 2 4 5 2 4 6 8 4 7 4 5 7 6 7 6 1↙ 有向网G的邻接矩阵为: 0 2 0 1 0 0 0 0 0 0 3 10 0 0 4 0 0 0 0 5 0 0 0 2 0 2 8 4

0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 1 0

输入源点下标:0↙

源点为:v=0 到各点的最短路径为: 0: min=0,path=0 0 1: min=2,path=0 1 2: min=3,path=0 3 2 3: min=1,path=0 3 4: min=3,path=0 3 4 5: min=6,path=0 3 6 5 6: min=5,path=0 3 6

程序运行中所建立的是图7.26(a)所示的有向网G的邻接矩阵，其输出结果是图7.26(b)所示的，从源点v0出发到各个顶点的最短路径长度以及路径上各个顶点的下标。该算法的时间复杂度为O(n2)。

7.5.2每一对顶点之间的最短路径

在有向网中，通过迪杰斯特拉(Dijkstra)算法可以求出从源点到其它各顶点的最短路径。对于具有n个顶点的有向网G，可以通过n次调用迪杰斯特拉算法求得每一对顶点之间的最短路径，其总的执行时间为O(n3)。此外还有另一种求解方法，这就是弗洛伊德(Floyd)算法。该算法的执行时间也是O(n3)，但是要比迪杰斯特拉(Dijkstra)算法简洁、清晰。

1．弗洛伊德(Floyd)算法思想

弗洛伊德(Floyd)算法的基本思想是：如果从vi到vj有弧ars[i][j]，则从vi到vj有一条长度为dist[i][j]=ars[i][j]的路径path[i][j]=。下面验证该路径是否为最短路径：

首先考虑是否存在（即和是否存在）。如果存在则比较ars[i][1]+ars[1][j]与ars[i][j]，取其中较小者作为从vi到vj的中间点序号不大于1的最短路径长度dist[i][j]并修改相应的路径path[i][j]。

然后在路径path[i][j]中再增加一个顶点v2，如果path[i][2]与path[2][j]均存在则比较dist[i][2]+dist[2][j]与dist[i][j]，取其中较小者作为从vi到vj的中间点序号不大于2的最短路径长度dist[i][j]并修改相应的路径path[i][j]。

之后在path[i][j]中再增加一个顶点v3重复以上过程。一般地讲，如果path[i][k]与path[k][j]分别是从vi到vk和vk到vj的中间顶点序号不大于k-1的最短路径，则比较dist[i][k]+dist[k][j]

-.207.-

第7章 图结构

与dist[i][j]，取较小者作为从vi到vj的中间点序号不大于k的最短路径长度dist[i][j]并修改相应的路径path[i][j]。

弗洛伊德(Floyd)算法递推地产生一个矩阵序列：

(dist(0)[i][j],path(0)[i][j])，(dist(1)[i][j],path(1)[i][j])，…，(dist(n)[i][j],path(n)[i][j])。

其中，(dist(k)[i][j],path(k)[i][j])分别表示从vi到vj的，中间顶点序号不大于k的，最短路径长度和路径。所以，Floyd算法就是逐步允许越来越多的顶点作为路径的中间顶点，直至所有可能的顶点均作为中间点为止。

取矩阵序列dist(k)[i][j]的初值为dist(0)[i][j]=arcs[i][j]，则已知dist(k-1)[i][j]求解dist(k)[i][j]的过程分以下两种情况：

(1) 如果从vi到vj的路径不经过vk，则dist(k)[i][j]=dist(k-1)[i][j]，path(k)[i][j]=path(k-1)[i][j]。 (2) 如果从vi到vj的路径经过vk，则比较dist(k-1)[i][k]+dist(k-1)[k][j]与dist(k-1)[i][j]，取较小者作为dist(k)[i][j]，并修改相应的路径path(k)[i][j]为：path(k-1)[i][j]或path(k-1)[i][k]+path(k-1)path[k][j]。

例如，对图7.28所示的有向网G，通过弗洛伊德(Floyd)算法，求其每一对顶点之间的最短路径长度dist[i][j]和最短路径path[i][j]。求解过程中dist、path的变化情况如图7.29所示。

?0411??0411??046??046??Dist=?602?Dist=?602?Dist=?502?

Dist0=?6021?23????????????300???370???370???370??

在图7.29中，Dist0与path0分别表示初始状态的vi、vj的最短距离及路径；Dist1与path1

分别表示加入顶点v0(即顶点a)以后顶点vi、vj的最短距离及路径；Dist2与path2分别表示加入顶点v1(即顶点b)以后顶点vi、vj的最短距离及路径；Dist3与path3分别表示加入顶点v2(即顶点c)以后顶点vi、vj的最短距离及路径。

2．弗洛伊德(Folyd)算法的实现

(1) 定义辅助数组dist[]与path[]的结构类型

struct Stack{int t,*s;}; //定义存储最短路径的栈类型

-.208.-

第7章 图结构

struct Min

{ int num; //有向网的结点个数 int *dist; //最短路径长度的数组指针 Stack *path; //存储路径的数组指针 };

(2) 数组的初始化操作

函数void InitMin(Min &min,MGraph G)的功能是，通过G的邻接矩阵对矩阵来初始化路径数组min。

void InitMin(Min &min,MGraph G) { int i,j,w; int num=G.vexnum; min.num=num; min.dist=new int[num*num]; //为最短距离矩阵dist分配空间 min.path=new Stack[num*num]; //为最短路径矩阵path分配空间 for(i=0;i { min.path[i*num+j].s[0]=i; min.path[i*num+j].s[1]=j; min.path[i*num+j].t+=2; } } } (3) 路径操作与显示输出

函数void Addpath(Stack &path,Stack path1,Stack path2)的功能是，实现对路径path[i][j]的连接操作：path[i][j]=path[i][k]+path[k][j]的运算。

void Addpath(Stack &path,Stack path1,Stack path2) { int t=0,i=0,j=1; while(i

函数void DisplyMin(Min min)的功能是，显示输出min中的最短路径长度min.dist和最短路径min.path。

void DisplyMin(Min min) { int i,j,k,t,n=min.num;

-.209.-

第7章 图结构

}

cout<<\最短距离矩阵dist为:\\n\for(i=0;i

{ for(j=0;j

cout<<\最短路径上的结点为:\\n\for(i=0;i

(4) 弗洛伊德算法实现

函数void Floyd(Min &min,MGraph G)的功能是，通过弗洛伊德算法求有向网G中每一对

顶点之间的最短路径及其长度到min中。

void Floyd(Min &min,MGraph G) { int i,j,k,n=G.vexnum; InitMin(min,G); for(k=0;k

在主函数中，首先通过函数调用“CreateGraph_MG(G,gk);”创建一个有向网G并显示输出G的邻接矩阵，再通过函数调用“Floyd(min,G);”求出G中任意两点间的最短路径到输min中，最后显示输出演示结果。

void main() {

-.210.-