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

1、一、概述0二、系统分析 0三、概要设计1四、详细设计44.1 建立图的存储结构 44.2 单源最短路径54.3 任意一对顶点之间的最短路径 6五、运行与测试 7参考文献10附录11交通咨询系统设计（最短路径问题）一、概述在交通网络日益发达的今天，针对人们关心的各种问题，利用计算机建立一个交通咨询系统。 在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的耗费。 这个交通咨询系统可以回答旅客提出的各种问题，例如：如何选择一条路径使得从 A城到B城途中中转次数最少； 如何选择一条路径使得从 A城到B城里程最短；如何选择一条路径使 得从A城到

2、B城花费最低等等的一系列问题。二、系统分析设计一个交通咨询系统， 能咨询从任何一个城市顶点到另一城市顶点之间的最短路径（ 里程 ） 、 最低花费或是最少时间等问题。 对于不同的咨询要求， 可输入城市间的路程、 所需时间或是所需费用等信息。针对最短路径问题， 在本系统中采用图的相关知识， 以解决在实际情况中的最短路径问题， 本系统中包括了建立图的存储结构、 单源最短问题、 对任意一对顶点间最短路径问题三个问题， 这对以上几个问题采用了迪杰斯特拉算法和弗洛伊德算法。 并未本系统设置一人性化的系统提示菜单，方便使用者的使用。三、概要设计可以将该系统大致分为三个部分：建立交通网络图的存储结构； 解决单

3、源最短路径问题； 实现两个城市顶点之间的最短路径问题。交通咨询系统依法意对短 工洛京任点最径 费德I顶问路杰特算3最路1迪斯拉法源短径立的储构 建图存结义迪杰斯特拉算法流图:弗洛伊德算法流图:四、详细设计4.1 建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，则G的邻接矩阵是具有 如下定义的 n 阶方阵。Wj,若(Vi,Vj)或 Vi,VjE(G)Ai, j0或 ，其他情况注： 一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有 n 个元素的一维数组来存储顶点信息 (下标

4、为 i 的元素存储顶点Vi 的信息) 。邻接矩阵的存储结构：#define MVNum 100 / 最大顶点数typedef structVertexType vexsMVNum;/ 顶点数组，类型假定为 char 型Adjmatrix arcsMVNumMVNum;/ 邻接矩阵，假定为 int 型 MGraph;注： 由于有向图的邻接矩阵是不对称的，故程序运行时只需要输 入所有有向边及其权值即可。4.2 单源最短路径单源最短路径问题：已知有向图 （ 带权 ） ，期望找出从某个源点 S 6 V到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图

5、G=（V,E）,其中V=1,2,n, cost是表 示G的邻接矩阵，costij 表示有向边<i,j> 的权。若不存在有向边<i,j> ，则costij的权为无穷大（这里取值为32767）。设S是一个集合，集合中一个元素表示一个顶点， 从源点到这些顶点的最短距离已经求出。设顶点Vi为源点，集合S的初态只包含顶点 V 数组dist记录 从源点 到 其它 各顶 点 当 前的 最短距离 ， 其 初值为 disti= costij , i=2 ,n。从S之外的顶点集合 V-S中选出一个顶点 w,使distw 的值最小。于是从源点到达 w只通过S中的顶点，把 w 加入集合 S 中

6、，调整 dist 中记录的从源点到 V-S 中每个顶点 v 的 距离： 从原来的 distv 和 distw+costwv 中选择较小的值作为新的 distv 。重复上述过程，直到 S 中包含 V 中其余顶点的最短路 径。最终结果是：S记录了从源点到该顶点存在最短路径的顶点集合，数组 dist 记录了从源点到 V 中其余各顶点之间的最短路径， path 是 最短路径的路径数组， 其中 pathi 表示从源点到顶点 i 之间的最短 路径的前驱顶点。4.3 任意一对顶点之间的最短路径任意顶点对之间的最短路径问题，是对于给定的有向网络图G=(V,E),要对G中任意一对顶点有序对，“V,W(V?W)&

7、quot;，找出V到W的最短路径。 而要解决这个问题， 可以依次把有向网络图中每个顶点作为源点， 重复执行前面的迪杰斯特拉算法n 次， 即可求得每对之间的最短路径。费洛伊德算法的基本思想：假设求从Vi 到 Vj 的最短路径。如果存在一条长度为 arcsij 的路径，该路径不一定是最短路径，还需要进行n次试探。首先考虑路径Vi,v i和vi,v j是否存在。如果存在，则比较路径Vi.Vj和Vi,Vi,Vj的路径长度，取长度较短者为当前所求得。该路径是中间顶点序号不大于 1 的最短路径。其次，考虑从Vi到Vj是否包含有顶点V2为中间顶点的路径 Vi,2,j,若没有，则说明从vi 到 vj 的当前最

8、短路径就是前一步求出的；若有，那么Vi,v 2, ,丫上可分解为Vi,山和V2,Vj,而这两条路径是前一次找到的中间点序号不大于 1 的最短路径， 将这两条路径长度相加就得到路径V,V2,帆的长度。将该长度与前一次中求得的从Vi 到 Vj 的中间顶点序号不大于1 的最短路径比较，取其长度较短者作为当前求得的从Vi 到 Vj 的中间顶点序号不大于2 的最短路径。依此类推直至顶点Vn加入当前从Vi到Vj的最短路径后，选出从Vi到Vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于 n， 所以 Vi 到 Vj 的中间顶点序号不大于n 的最短路径， 已考虑了所有顶点作为中间顶点的可能性，

9、因此，它就是Vi 到 Vj 的最短路径五、运行与测试测试实例1:利用如下图所示的有向图来测试实例1运行结果:.exe、数和边数nj 及”：点的顶边也祭县 0 3 7 6 4 2 1 国 1117736 XX 3 7 6 4 2 1 41-刖)九乙I ” J.TFfTF 1 1 7 7 3 6-26向图堂耦蓊褊各径上青选择点或2,选择。退出， 泉单源境径，输入源点"门 ，各径长度路在01452<-3<-1133<-1914<-?<-1136 5m716<-2<-3<-1177<-1*求城市之间最短路径，1佳二金越市到扬有城市殷基豆陶

10、至2 .耒任意的两个城币之间的最短睹但 请选择式或2,选径。退出：御入遮点（或起点、和终点:七。*，5双顶点1至5最短;南径路径是山一74一5径路长度门36实例2运行结果:青选择n或2,选#0退出:&迫12062<-3<-i6953<-17044<-120185m22746<-3<-113557<-4<-1卷 DUF-m 短短 in瞽取 的的 币间 城Z 有市 续 到个 市两 爵 金忌 一任 i清选择或对选择且退出:L .求KJCiCMX箕宜旄KJCiCM云_国 市 反二|用最决眼豺交HXHHXHKMjHXHH工寸£城市到度有城

11、市殷粼里L 求任意窗两个城市芝间的量短路径膏选择:1或2,选择A退出:肺入源点 或顶点5&起点）和终点：u,w；5K7最粗陈痉膝径是;5£一347径路长度:2323M注XXXHHXHXHK求城市国最短路径*H* + *Y*短短 的的 ,巾间 城Z 有市 到个 市两请选择：工或2,选择0退出：2轴入源点（或起点4和终点二。3二乙2次顶点7至r2最短路径路径是：7432轻路长度；1SH六、总结与心得该课程设计主要是从日常生活中经常遇到的交通网络问题入手， 进而利用计算机去建立一个交通咨询系统，以处理和解决旅客们关心 的各种问题（当然此次试验最终主要解决的问题是： 最短路径问题）。

12、这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多的问题我们可以通过树的相关知识来解决，特别 是在解决最短路径问题中，显得尤为重要。经过着次实验，我了解到了关于树的有关算法，如：迪杰斯特拉 算法、弗洛伊德算法等，对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计苏仕华.极械工业出版社.附录#include<stdio.h>#include<stdlib.h>#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char

13、VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(MGraph * G ,int n,int e)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;p

14、rintf(" 输入 %d 条边的 i.j 及 w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf(" 有向图的存储结构建立完毕！ n");void Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;v<=n;v+)Sv=FALSE;D2v=G->arcsv1v;

15、if(D2v<Maxint)p2v=v1;elsep2v=0;)D2v1=0; Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+)if(!Sw && D2w<min)v=w;min=D2w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw && (D2v+G->arcsvw<D2w) D2w=D2v+G->arcsvw;p2w=v;printf("路径长度路径n");for(i=1;i<=n;i+)printf("%

16、5d",D2i);printf("%5d",i);v=p2i;while(v!=0)printf("<-%d",v);v=p2v;printf("n");void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if( G->arcsij!=Maxint)pij=j;elsepij=0;Dij=G->arcsij;for(k=1;k<=n;k+)for(i=1;i<=n;i+)for(j=1;j&

17、lt;=n;j+)if(Dik+Dkj<Dij)Dij=Dik+Dkj;pij=pik；)void main()(MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf("输入图中顶点个数和边数n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf("*求城市之间最短路径 *n");printf("=n");printf(

18、"1.求一个城市到所有城市的最短路径n");printf("2.求任意的两个城市之间的最短路径n");printf("=n");printf("请选择：1或2,选择0退出:n");scanf("%d",&xz);if (xz=2)Floyd(G,n);printf("输入源点(或起点)和终点 ：v,w:");scanf("%d,%d",&v,&w);k=pvw;if (k=0) printf("顶点 %d 到 %d 无路径！n",v,