交通咨询系统中的最短路径设计

1、东北大学秦皇岛分校数据结构课程设计交通咨询系统设计业计算机科学与技术1=指导教师日 期一、需求分析设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一城市顶点之间的最短路 径（里程）或最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程或所 需时间或所需费用。本设计共分三部分，一是建立交通网络图的存储结构；二是解决单源最短路径问题；三 是实现任两个城市顶点之间的最短路径问题。1.1.1建立图的存储结构邻接矩阵是表示图形中顶点之间相邻关系的矩阵。图的邻接矩阵是定义如下的n阶方 阵：浴一旦一不囱 士 占隹 V = ，V , , V 设G=（V，E） 是 |图，结点集为 1 2 n。

2、（w ），当（V , V）或 G EG的邻接矩阵A = （a ） , a = 7心顶、顶 ，ij n乂nij0或 3，当（V , V）或 W EIi ji j当邻接矩阵的行表头、列表头顺序一定时，一个图的邻接矩阵表示是唯一的。图的邻接矩阵表示，除了需用一个二维数组存储顶点之间的相邻关系的邻接矩阵外，通 常还需要使用一个具有n个元素的一维数组来存储顶点信息，其中下标为i的元素存储顶点 i的信息。因此，图的邻接矩阵的存储结构定义如下：#definf MVNum 50 /最大顶点数typedef structVertexType vexsMVNum;/顶点数组，类型假定为char型Adjmatrix

3、 arcsMVNumMVNum;/邻接矩阵，假定为 int 型MGraph;1.1.2单源最短路径最短路径的提法很多。在这里先讨论单源最短路径问题：即已知有向图（带权），我们 希望找出从某个源点SG V到G中其余各顶点的最短路径。为了叙述方便，我们把路径上的开始点称为源点，路径的最后一个顶点为终点。那么，如何求得给定有向图的单源最短路径呢？迪杰斯特拉（Dijkstra）提出按路径长 度递增产生诸点的最短路径算法，称之为迪杰斯特拉算法。迪杰斯特拉算法求最短路径的实现思想是：设G=（V，E）是一个有向图，结点集为，V = vi,v2, ,v，cost是表示G的邻接矩阵，costij表示有向边的权。

4、若不 存在有向边，则costij的权为无穷大（这里取值为32767）。设S是一个集合，其 中的每个元素表示一个顶点，从源点到这些顶点的最短距离已经求出。设顶点七为源点， 集合S的初态只包含一个元素，即顶点七。数组dist记录从源点到其他顶点当前的最短距 离，其初值为disti=costVi,i=1,2,n。从S之外的顶点集合V-S中选出一个顶点w，使distw的值最小。于是从源点到达w只通过S中顶点，把w加入集合S中，调整 dist中记录的从源点到V-S中每个顶点v的距离:从原来的distv和distw+costwv 中选择较小的值作为新的distv。重复上述过程，直到V-S为空。最终结果是：

5、S记录了从源点到该顶点存在最短路径的顶点集合，数组dist记录了源 点到V中其余各顶点之间的最短路径，path是最短路径的路径数组，其中pathi表示从源 点到顶点i之间的最短路径的前驱顶点。因此，迪杰斯特拉算法可用自然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值;Sv1=TRUE; Dv1=0；/S集初始时只有源点，源点到源点的距离为0；While （S集中顶点数n） 开始循环，每次求得V1到某个v顶点的最短路径，并加v到S集中； Sv=TRUE；更新当前最短路径及距离；1.1.3任意一对顶点间最短路径任意一对顶点间最短路径问题，是对于给定的有向网络图G=（V，E），要

6、对G中任意一 对顶点有序对“v,w（v w） ”，找出v到w的最短路径。要解决这个问题，我们可以依次把有向网络图中每个顶点作为源点，重复执行前面讨论 的迪杰斯特拉算法n次，即可以求得每对顶点之间的最短路径。这里还可以用另外一种方法，称作费洛伊德（Floyd）算法。费洛伊德（Floyd）算法算法的基本思想是：假设求从顶点v.到v.的最短路径。如果从 vi到v.存在一条长度为arcsij的路径，该路径不一定是最短路径，还需要进行n次试 探。首先考虑路径v ,v 和v ,v 是否存在。如果存在，则比较v ,v 和 v,v,v 的路 TOC o 1-5 h z i 11 ji ji 1 j径长度，取长

7、度较短者为当前所求得的最短路径。该路径是中间顶点序号不大于1的最短路 径。其次，考虑从v到v是否包含有顶点v为中间顶点的路径v,v,v，若没有，i j2i2j则说明从v到v的当前最短路径就是前一步求出的；若有，那么v,v,v可分解为i ji2jv.,七和v2，,v,而这两条路径是前一次找到的中间顶点序号不大于1的最短路径，将 这两条路径长度相加就得到路径v.,v2，,v.的长度。将该长度与前一次中求出的从v. 到v.的中间顶点序号不大于1的最短路径比较；取其长度较短者作为当前求得的从v.到vj 的中间顶点序号不大于2的最短路径。依此类推，直到顶点vn加入当前从v到v.的最短路 径后，选出从v到

8、v.的中间顶点序号不大于n的最短路径为止。由于图G中顶点序号不大 于n，所以v到v.的中间顶点序号不大于n的最短路径，已考虑了所有顶点作为中间顶点的 可能性，因此，它就是v.到v的最短路径。1.2程序流程图j/箍出答n算桂的结果二、详细设计2.1建立有向图的存储结构void CreateMGraph(MGraph * G, int n, int e)int i,j,k,w;for(i=1;ivexsi=(char)i;for (i=1;i=n;i+)for(j=1;jarcsij=Maxint;printf(输入%d 条边的 i,j 及 w:n,e);for (k=1;karcsij=w;pr

9、intf(有向图建立完毕n)；2.2迪杰斯特拉算法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;elseP2v=0;D2v1=0;Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;P2w=v;printf(-路径长度路径n)；

10、for (i=1;i=n;i+)printf(%5d”,D2i);printf(5d，i);v=P2i;while (v!=0)printf(-%d,v);v=P2v;printf(n)；2.3费洛伊德算法void Floyd(MGraph *G, int n)int i,j,k,v,w;for (i=1;i=n;i+)for(j=1;jarcsij!=Maxint)Pij=j;elsePij=0;Dij=G-arcsij;for (k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)if(Dik+DkjDij)Dij=Dik+Dkj;Pij=Pik;2.4运行主

11、控程序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(1.求一个城市到所有城市的最短路径n)； printf(2.求任意的两个城市之间的最短路径n); printf(请选择：1或2,选择0退出：)； scanf(%d,&xz);if(xz=2)Floyd(G,n);prin

12、tf(输入起点和终点:v,w:)；scanf(d,%d，&v,&w);k=Pvw;if(k=0)printf(顶点 %d 到 %d 无路径!n”,v,w);elseprintf(从顶点d到d的最短路径是:%d”,v,w,v);while(k!=w)printf(一“2%d,k);k=Pkw;printf(一“2%d,w);printf(路径长度:%dn”,Dvw);else if(xz=1)printf(求单源路径，输入源点v :);scanf(%d,&v);Dijkstra(G,v,n);printf(结束求最短路径)；三、调试分析编译：在第一次编译时出现了很多错误，是因为我对C语言的不熟练

13、，比如调用费洛伊 德算法时出现了调用的错误，找了好久，才改正过来，还有就是for语句的运用，由于本次 程序要用很多for循环，我把一次for循环放到了上面for循环中，导致程序不能正确输出 结果。最后把调到外面才OK。四、测试结果交通咨询系统通过迪杰斯特拉算法得出每一个城市到所有城市的最短路径，然后通过费 洛伊德算法得出任意两个城市间最短路径。本程序的运行环境为DOS操作系统，执行文件为 交通咨询.exe。进入程序后，即显示文本的操作界面：,D:41OO224liuliulin.exe酶入图中顶点个数和边数n，e：输入定点数和边数后，依次输入有向边，以及两点间的距离，用逗号间隔开，回车换行，

14、当有向图输入完全时，进入菜单t *月- 半车 曰瞽取 市间 城之 .代市 到个 市两 蕾 一佑 1TT D:4100224liuliulin.exe选择你要进行的模式，求一个城市到所有城市的最短路径输入1，回车进入该模式，输 入你所要求的城市代表的顶点数，回车确认。求任意的两个城市之间的最短路径输入2,回车确认进入该模式，输入两座城市代表的 顶点数，以逗号间隔开，回车确认。运行结果：下面是城市交通图广州BH D:4100224liuliLilir.exe可 ,D:4100224liuliulin.exet 丸口熨口 HTKnTK- -B-5M 车/ 曰簪取 市间 城之 .有市 到个 市两 蕾

15、-伍 1请选择：1或2,选择。:退出：1 fel起点：1a 1206 695 704 2018 2274 13552-3-l3-l4-l5-2-3-l6-3-l7-4-l求城市之间的最断路径t 丸口熨口 HTKnTK 一口1.一豆 车/ 曰簪取 市间 城之 .有市 到个 市两 蕾 -伍 122746-3-113557-42-3-路径长度2323请选择：,或2, 谿卷辙的最圭整谖是:5求赢币N间的豪断路径t 鬼口鬼口 nTKHJ -R-HM 牛|. 曰馨取 市间 城之 .句市 到个 市两 蕾 -的 1遣粪择: 求掌源 路径长695511a3491323 1579 1000或2,选择。：退出：1

16、输入起点。=3 至1-32-334-35-2-36-37-4347 破市之间的基断路径路径长度：姑117-6曰1或2, 选择日:退出：1 至，输入起点u :& 路径1-3-62-3-63-64-3-65-610007-4-3求城市之间的最断路径D:4100224liuliulin.exe择F D:4100224liuliulir.exe1 2t ._口.-h-.-n- HTKnTK 一口1.一一口_ 车,. 曰瞽取 市间 城之 有市 到个 市两 蕾 -的i 口.-k./-.口 nTKHTK- 一口,一一 口,!.一 牛.车I1. 馨取 市间 城之 有市 到个 市两亘亘甚.X隶任赛路径长E 22

17、74 2090 1579 1928 2368 0 1385求城市之间的最断路径口!? nTKHTK- 一口,一一 口!.- 圭车. 曰簪取 的的 市间 城Z .句市 到个 市两 蕾 -佑 12 ?- 成路继 1短键 质 i结请六、附录#include#include#define MVNum 100/最大顶点数#define Maxint 35000enum booleanFALSE,TRUE;typedef char Vertextype;typedef int Adjmatrix;typedef struct Vertextype vexsMVNum;/顶点数组，类型假定为char型Adj

18、matrix arcsMVNum MVNum; / 邻接矩阵，假定为 int 型 MGraph;int D1MVNum, p1MVNum;int DMVNumMVNum,pMVNumMVNum;文件名save.cvoid CreateMGraph(MGraph *G,int n,int e) 采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数int i,j,k,w;for(i=1;ivexsi = (char)i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint; / 初始化邻接矩阵printf (输入%d 条边的 i,j 及 w: n,e);for(k=

19、1;karcsij=w; printf (有向图的存储结构建立完毕！ n);文件名:dijkstra.c(迪杰斯特拉算法)void Dijkstra(MGraph *G, int v1,int n) 用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路径pv及其权Dv设G是有向图的邻接矩阵，若边不存在，则Gij=Maxint/Sv为真当且仅当v属于S，及以求的从v1到v的最短路径int D2MVNum, p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v;/置初始的最短路径值if(D2v Maxint)p2v=v1;/

20、v1是的前趋(双亲)elsep2v=0;/v 无前趋/ End_forD2v1=0;Sv1=TRUE;/S集初始时只有源点，源点到源点的距离为0开始循环，每次求的V1到某个V顶点的最短路径，并加V到S集中for(i=2;in;i+)(其余n-1个顶点min=Maxint; /当前所知离v1顶点的最近距离，设初值为8 for(w=1;w=n;w+)/对所有顶点检查if(!Sw & D2wmin) /找离v1最近的顶点w,并将其赋给v,距离赋给min v=w;/在S集之外的离v1最近的顶点序号min=D2w;/最近的距离/W顶点距离V1顶点更近Sv=TRUE;/将 v 并入 S 集for(w=1;warcsvwarcsvw;更新 D2wp2w=v; /En