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

1、邻接矩阵就是表示图形中顶点之间相邻关系的矩阵。设G=（V,E）就是具有n个顶点的图,则G的邻接矩阵就是具有如下定义的n阶方阵。注:一个图的邻接矩阵表示就是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储顶点的信息）。邻接矩阵的存储结构:#define MVNum 100 /最大顶点数typedef struct VertexType vexsMVNum;/顶点数组,类型假定为char型 Adjmatrix arcsMVNumMVNum;/邻接矩阵,假定为int型MGraph;由于有向图的邻接矩阵就是不对称的,

2、故程序运行时只需要输入所有有向边及其权值即可。4、2单源最短路径单源最短路径问题:已知有向图（带权）,期望找出从某个源点SV到G中其余各顶点的最短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想:设有向图G=（V,E）,其中V=1,2,n,cost就是表示G的邻接矩阵, costij表示有向边的权。若不存在有向边,则costij 的权为无穷大（这里取值为32767）。设S就是一个集合,集合中一个元素表示一个顶点,从源点到这些顶点的最短距离已经求出。设顶点V1为源点,集合S的初态只包含顶点V1。数组dist记录从源点到其它各顶点当前的最短距离,其初值为disti= cost

3、ij,i=2,n。从S之外的顶点集合V-S中选出一个顶点w,使distw 的值最小。于就是从源点到达w只通过S中的顶点,把w加入集合S中,调整dist中记录的从源点到V-S中每个顶点v的距离:从原来的distv与distw+costwv中选择较小的值作为新的distv。重复上述过程,直到S中包含V中其余顶点的最短路径。 最终结果就是:S记录了从源点到该顶点存在最短路径的顶点集合,数组dist记录了从源点到V中其余各顶点之间的最短路径,path就是最短路径的路径数组,其中pathi表示从源点到顶点i之间的最短路径的前驱顶点。4、3任意一对顶点之间的最短路径 任意顶点对之间的最短路径问题,就是对于

4、给定的有向网络图G=（V,E）,要对G中任意一对顶点有序对,“V,W（VW）”,找出V到W的最短路径。而要解决这个问题,可以依次把有向网络图中每个顶点作为源点,重复执行前面的迪杰斯特拉算法n次,即可求得每对之间的最短路径。 费洛伊德算法的基本思想:假设求从Vi到Vj的最短路径。如果存在一条长度为arcsij的路径,该路径不一定就是最短路径,还需要进行n次试探。首先考虑路径与就是否存在。如果存在,则比较路径vi,v1,vj的路径长度,取长度较短者为当前所求得。该路径就是中间顶点序号不大于1的最短路径。其次,考虑从vi到vj就是否包含有顶点v2为中间顶点的路径,若没有,则说明从vi到vj的当前最短

5、路径就就是前一步求出的;若有,那么可分解为v2,vj,而这两条路径就是前一次找到的中间点序号不大于1的最短路径,将这两条路径长度相加就得到路径的长度。将该长度与前一次中求得的从vi到vj的中间顶点序号不大于1的最短路径比较,取其长度较短者作为当前求得的从vi到vj的中间顶点序号不大于2的最短路径。依此类推直至顶点vn加入当前从vi到vj的最短路径后,选出从vi到vj的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大于n,所以vi到vj的中间顶点序号不大于n的最短路径,已考虑了所有顶点作为中间顶点的可能性,因此,它就就是vi到vj的最短路径。五、运行与测试测试实例1:利用如下图所示的有

6、向图来测试测试实例2:利用下图求交通网络图（无向图）的最短路径。实例1运行结果:实例2运行结果:六、总结与心得该课程设计主要就是从日常生活中经常遇到的交通网络问题入手,进而利用计算机去建立一个交通咨询系统,以处理与解决旅客们关心的各种问题（当然此次试验最终主要解决的问题就是:最短路径问题）。这次试验中我深刻的了解到了树在计算机中的应用就是如何的神奇与灵活,对于很多的问题我们可以通过树的相关知识来解决,特别就是在解决最短路径问题中,显得尤为重要。经过着次实验,我了解到了关于树的有关算法,如:迪杰斯特拉算法、弗洛伊德算法等,对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏、清华大学出版社

7、、【2】数据结构课程设计苏仕华、极械工业出版社、附录#includestdlib、h#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structint D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph（MGraph * G,int n,int e） int i,j,k,w; for（i=1;ivexsi=（char）i; for（j=1;jar

8、csij=Maxint; printf（输入%d条边的i、j及w:n,e）; for（k=1;k=e;k+） scanf（%d,%d,%d,&i,&j,&w）;arcsij=w; 有向图的存储结构建立完毕！）;void Dijkstra（MGraph *G,int v1,int n） int D2MVNum,p2MVNum; int v,i,w,min; enum boolean SMVNum; for（v=1;varcsv1v; if（D2vMaxint） p2v=v1; else p2v=0; D2v1=0; Sv1=TRUE; for（i=2;n;i+） min=Maxint; for（

9、w=1;ww+） if（!Sw & D2warcsvwarcsvw; p2w=v; printf（路径长度 路径n%5d,D2i）;,i）;v=p2i; while（v!=0） printf（arcsij!=Maxint） pij=j; else pij=0; Dij=G-arcsij;k+） for（i=1; for（j=1; if（Dik+DkjDij） Dij=Dik+Dkj; pij=pik; void main（） MGraph *G; int m,n,e,v,w,k; int xz=1; G=（MGraph *）malloc（sizeof（MGraph）;输入图中顶点个数与边数n,

10、e: scanf（%d,%dn,&e）; CreateMGraph（G,n,e）; while（xz!*求城市之间最短路径*n=n1、求一个城市到所有城市的最短路径n2、求任意的两个城市之间的最短路径n请选择 :1或2,选择0退出:%dxz）; if （xz=2） Floyd（G,n）; printf（输入源点（或起点）与终点:v,w: scanf（v,& k=pvw; if （k=0） printf（顶点%d 到 %d 无路径!,v,w）; else从顶点%d 到 %d 最短路径路径就是:,v,w,v）; while （k!=w） printf（-%d,k）; k=pkw;,w）;径路长度:%dn,Dvw）; if（xz=1）求单源路径,输入源点v :v）; Dijkstra（G,v,n）;结束求最短路径,再见!