第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]=
首先考虑
然后在路径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
函数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.-