《数据结构课程设计》最短路径问题实验报告(2)

四、详细设计

4.1建立图的存储结构

定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。

?Wij，若(Vi,Vj)或?Vi,Vj??E(G)? A[i,j]???0或?，其他情况?注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点Vi的信息）。 邻接矩阵的存储结构：

#define MVNum 100 //最大顶点数 typedef struct {

VertexType vexs[MVNum];//顶点数组，类型假定为char型 Adjmatrix arcs[MVNum][MVNum];//邻接矩阵，假定为int型 }MGraph;

注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。

5

4.2单源最短路径

单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。

迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。 算法思想：设有向图G=(V,E)，其中V={1,2，……n}，cost是表示G的邻接矩阵，

cost[i][j]表示有向边的权。若不存在有向边，则cost[i][j] 的权为无穷大（这里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离，其初值为dist[i]= cost[i][j]，i=2，……n。从S之外的顶点集合V-S中选出一个顶点w，使dist[w] 的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，调整dist中记录的从源点到V-S中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中选择较小的值作为新的dist[v]。重复上述过程，直到S中包含V中其余顶点的最短路径。

最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了从源点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中path[i]表示从源点到顶点i之间的最短路径的前驱顶点。

6

4.3任意一对顶点之间的最短路径

任意顶点对之间的最短路径问题，是对于给定的有向网络图

G=(V,E),要对G中任意一对顶点有序对，“V,W(V≠W)”，找出V到W的最短路径。而要解决这个问题，可以依次把有向网络图中每个顶点作为源点，重复执行前面的迪杰斯特拉算法n次，即可求得每对之间的最短路径。

费洛伊德算法的基本思想：假设求从Vi到Vj的最短路径。如果存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径和是否存在。如果存在，则比较路径和的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于1的最短路径。其次，考虑从vi到vj是否包含有顶点v2为中间顶点的路径< vi,…,v2,…,vj>，若没有，则说明从vi到vj的当前最短路径就是前一步求出的；若有，那么可分解为和，而这两条路径是前一次找到的中间点序号不大于1的最短路径，将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从vi到vj的中间顶点序号不大于1的最短路径比较，取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推……直至顶点vn加入当前从vi到vj的最短路径后，选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n，所以vi到vj的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的可能性，因此，它就是vi到vj的最短

7

路径。

五、运行与测试

测试实例1：利用如下图所示的有向图来测试 1 13 3 17 7 61 32 76 74 2 6 64 26 4 56 45 5 测试实例2：利用下图求交通网络图（无向图）的最短路径。 2553 北京 1 西安 704 2 695 812 4 成都 511 3 349 5 郑州 651 1579 2368 1385 7 上海 广州 6

实例1运行结果：

徐州8

9