单源点最短路径算法的实现 数据结构 课程设计.docx

数据结构课程设计设计说明书单源点最短路径算法的实现学生姓名 学 号 班 级 成 绩 指导教师 数学与计算机科学学院2014年3月7日课程设计任务书2013 2014学年第2学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目：单源点最短路径算法的实 完成期限：自2014 年旗月 24日至 2014年工月 7 日共2 周设计依据、要求及主要内容（可另加附页）：最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然 后依次把未知集合的顶点按照最短路径（特别强调一下是源点到该顶点的路径权重和，不仅 仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。 在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径 和权重。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路 径问题，本系统中包括了建立图的存储结构、单源最短问题，这对以上几个问题采用了迪杰 斯特拉算法。并为本系统设置一人性化的系统提示菜单，方便使用者的使用。本课程设计中主要完成以下内容：L 建立图的存储结构。2. 解决单源最短路径问题。五 实现两个顶点之间的最短路径问题。基本要求如下:1. 程序设计界面友好；2. 设计思想阐述清晰；3. 算法流程图正确；4. 软件测试方案合理、有效。指导教师（签字）:教研室负责人（签字）:批准日期：年 月 日课程设计评阅评语：指导老师签名：年 月本软件以VC+作为开发平台，设计了关于从某个单一原点到任意顶点的一个类似于 查询，咨询系统的软件。它能够准确快速的计算出从某个单一原点到任意顶点的最短路径以 及路径长度。该类软件目前广泛运用于城市交通运输系统，为人们出行带来了方便。关键字：VC+；最短路径；迪杰斯特拉算法；目录目录1-1、课题描述4-2、问题分析与设计思想2-3、概要设计-4-4、详细设计-6-4.1建立图的存储结构6 -4.2单源最短路径-6-5、程序编码£6、程序调试和测试12-7、总结16-参考文献16-1、课题描述在城市交通网络日益发达的今天，针对人们出行关心的各种问题，利用计算机软件建 立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边 表示各个城市之间的交通关系，所带权值为两个城市间的距离。2、问题分析与设计思想问题分析：可以将该系统大致分为两个部分： 建立网络图的存储结构：定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。 解决单源最短路径问题：单源最短路径问题：已知有向图(带权)，期望找出从某个源点SeV到G中其余各顶点 的最短路径。设计思想：Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法。首先，引进一个辅助 向量D,它的每个分量Di表示当前所找到的从源点v到每个终点vi的最短路径长度。 它的初始状态为：若v到vi有弧，则Di为弧上的权值，否则Di为无穷大。显然， 长度为:Dj = MinDi I vi属于V的路径就是从v出发的长度最短的一条路径。此路 径为(v, vi)。那么，长度次短的路径是哪一条呢？假设该次短路径的终点是vk，则可 以证明，这条路径或者是(v, vk)，或者是(v, vj, vk)。它的长度或者是从v到vk的弧上的 权值，或者是Dj和从vj到vk的弧上的权值之和。j为寻找下一 个顶点的变量图2.1 Dijkstr算法流程图3、概要设计存在一条从i到j的最短路径(ViVk,Vj), Vk是Vj前面的一顶点。那么(Vi.Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最 短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的 顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离 distj=mindistj,disti+matrixij 。根据这种思路，假设存在G=<V,E>，源顶点为V0，U=V0,disti记录V0到i的最短距离，pathi 记录从V0到i路径上的i前面的一个顶点。1. 从V-U中选择使disti值最小的顶点i，将i加入到U中；2. 更新与i直接相邻顶点的dist值。(distj=mindistj,disti+matrixij)3 .知道U=V，停止。流程图:i+i>n修改最短路径和距离输出结果图3.1最短路径4、详细设计4.1建立图的存储结构定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。设G=（V,E是具 有n个顶点的图，则G的邻接矩阵是具有如下定义的n阶方阵。注：一个图的邻接矩阵表示是唯一的！其表示需要用一个二维数组存储顶点之间相邻关系的 邻接矩阵并且还需要用一个具有n个元素的一维数组来存储顶点信息（下标为i的元素存储 顶点的信息）。邻接矩阵的存储结构：#define MVNum 100 /最大顶点数typedef structVertexType vexsMVNum;/页点数组，类型假定为char型Adjmatrix arcsMVNumMVNum;/邻接矩阵，假定为 int 型MGraph;注：由于有向图的邻接矩阵是不对称的，故程序运行时只需要输入所有有向边及其权值即可。4.2单源最短路径单源最短路径问题：已知有向图（带权），期望找出从某个源点SEV到G中其余各顶点的最 短路径。迪杰斯特拉算法即按路径长度递增产生诸顶点的最短路径算法。算法思想：设有向图G=（V,E），其中V=1,2，n，cost是表示G的邻接矩阵， costij表示有向边i,j的权。若不存在有向边i,j，则costij的权为无穷大（这里 取值为32767）。设S是一个集合，集合中一个元素表示一个顶点，从源点到这些顶点 的最短距离已经求出。设顶点V1为源点，集合S的初态只包含顶点V1。数组dist记 录从源点到其它各顶点当前的最短距离，其初值为disti= costij，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之间的最短路径的前驱顶点。5、程序编码#include<stdio.h>#include<stdlib.h>#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char 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;printf("输入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;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("%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<=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");:n")；printf(”=printf("1.求一个城市到所有城市的最短路径/);printf("2.求任意的两个城市之间的最短路径/);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 至 U %d 无路径!n”,v,w);elseprintf("从顶点d至U %d最短路径路径是:d”,v,w,v);while (k!=w)printf("-%d”,k);k=pkw;printf("-%d”,w);printf("径路长度:dn”,Dvw);elseif(xz=1)printf(-求单源路径，输入源点v :");scanf("%d”,&v);Dijkstra(G,v,n);printf("结束求最短路径，再见!n");6、程序调试和测试测试实例1：利用如下图所示的有向图来测试。图5.1有向图测试实例1运行结果:C:Use rsLenovoDes kto pccccDe b u g C 在 pp1 .exe输入图中顶点个数和边数n ,白：7,1。1。输入1。条边的i. j及w：1,3,131,7,177,6,767,4,743,2,326,1,616,4,644,5,455,6,562,6,26有向图的存储结构建立完毕！ 求城市之间最短路径1 .求一个城市到所有城市的最短路径请输入1,选择。退出：1求单源路径，输入源点。：1路径长度路径01452<-3<-1133<-1914<-7<-11365<-4<-7<-1716<-2<-3<-1177<-1芫XXX芫XXX芫XXX求城市之J可最.短路；样:XX芫XXX芫XXX芫X1 .求一个城市到所有城市的最短路径请输入1,选择。退出:TTII vlj图5.2有向图测试运行结果测试实例2：利用下图求无向图的最短路径。5.3无向图测试EX"C:U se rsLenovoDes kto pccccDe b u g C 在 pp1 .exe输入图中顶点个数和边数。般：了，1818输入18条边的i. j及w：1,3,6953,1,6951,4,7044,1,7042,3,5113,2,5112,5,8125,2,8123,4,3494,3,3493,6,15796,3,15794,7,6517,4,6515,6,2368G,5,23686,7,1385Y g 1385肴向图的存储结构建立完毕!_拭*天拜拭*天拜拭*天拜求士成市之I司晶矢日路'怜天关拭*天拜拭*天拜拭*1 .求一个城市到所有城市的最短路径请输入1,选择。退出： 1路径12<-3<-13<-14<-1 5<-2<-3<-1求单源路径，输入源点U ：1 路径长度 0 1206 695 704图5.4无向图测试结果7、总结该课程设计主要是从日常生活中经常遇到的交通网络问题入手，进而利用计算机去 建立一个类似交通咨询系统，以处理和解决人们关心的各种问题（当然此次试验最终主要解决的问题是：最短路径问题）。这次试验中我深刻的了解到了树在计算机中的应用是如何的神奇与灵活，对于很多 的问题我们可以通过树的相关知识来解决，特别是在解决最短路径问题中，显得尤为 重要。经过着次实验，我了解到了关于树的有关算法，如：图的存储结构，迪杰斯特拉算法 等，对树的学习有了一个更深的了解。参考文献【1】数据结构严蔚敏.清华大学出版社.【2】数据结构课程设计苏仕华.极械工业出版社.