课程设计单源点最短路径算法的实现

1、数据结构课程设计设计说明书单源点最短路径算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2015 年 1 月 2 日数据结构 课程设计评阅书题目单源点最短路径算法的实现学生姓名学 号指导教师评语及成绩成绩：教师签名：年月日教研室意见总成绩：室主任签名：年月日课程设计任务书2014 2015学年第1学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目 单源点最短路径算法的实现完成期 限：自 2014 年V2_月_22_日至 2015 年月_2_ 日共_2_周 设计内容及要求：最短路径问题已经被应用到GIS、GPS等信息管理系统中，为人们生活带来了很大便利。它属于图结构问题，其解

2、决方法也有不少（如Dijkstra、 A-star）。单源点最短路径问题解决的是既定起点的情况下，寻求该点到图中其它顶点的最短路径。请用C/C+语言的结构体、指针、数据结构等基础知识，编写程序实现图的结构定义、图的存储，以及求解 单源点最短路径。设计过程以及写作要求如下：（1） 要针对本题目，认真研究所设计的内容，用简明扼要的语言描述课题，给出课题的基本内容及要求；（2） 根据数据结构的相关知识给出实现建立任意m个顶点n条边的图算法、按照用 户给定的源点和目标点，求出它们间的最短路径（打印出来）算法的基本策略及思路；（3） 给出较为详尽数据结构与算法，算法可以用流程图、伪代码等描述手段进行描述

3、；（4） 给出一个完整的算法实现的 C/C+程序，算法中的各子算法要力求用函数来实现；（5）对编写的程序要进行详尽的测试分析；（6）对本课题的设计工作要进行一个完整深刻的总结。最终设计成果形式为：1、设计软件一套；2、撰写一份课程设计说明书一份，打印并装订成册。指导教师（签字）：批准日期：年 月教研室主任（签字）摘要本系统以VC+乍为软件开发环境，C语言作为程序开发语言， 邻接矩阵作为存储结构, 设计与实现了最短路径运算。该系统实现了有向图的存储、最短路径的运算等主要功能。 依照该系统可以解决生活中许多问题，比如交通路线的选择，工程时间的预算等等，让人 们可以做出合理的选择。本系统通过分析课题

4、的背景、意义、要求，分别从课题描述、逻 辑设计、算法设计、调试与测试等各个方面详细介绍了系统的设计与实现过程，最后对系 统的完成情况进行了总结。界面清晰，操作简单，易于用户接受。关键词 ：VC+; 邻接矩阵 ; 最短路径目录1 课题描述 12 问题分析与任务定义 22.1 问题分析 22.2 任务定义 23 算法设计 33.1 图的邻接矩阵的存储结构 33.2 Dijkstra 算法思想 44 系统逻辑设计 54.1 主函数流程图如图 4.1 所示 54.2 Create 函数流程图如图 4.2 所示 64.3 Dijkstra 函数流程图如图4.3 所示 85 源代码 116 调试与测试 1

5、46.1 合法数据输入 146.2 非法数据输入 15总结 16参考文献 171 课题描述 乘车旅行的人大多数都希望找出到目的地尽可能短，花费少的行程，那么如何找出从 出发点到目的地的最短路径？由于路径比较多，所以用手工计算起来比较复杂，抽象，因 此人们用计算机语言代替手工计算来求得最短路径。而在计算机语言中迪杰斯拉算法比较 常用，简捷，故人们经常借助计算机程序用迪杰斯拉算法求得单源点的最短路径，这样可 以广泛的提高效率，而且条理清晰，通俗易懂2 问题分析与任务定义2.1 问题分析本系统是要解决的是单源点最短路径问题，设计程序，实现最短路径的求法，系统需要达到的主要功能如下：(1) 编写算法能

6、够建立带权图，并能够用 Dijkstra 算法求该图的最短路径。(2) 能够选择图上的任意一顶点做为开始节点。最短路径输出不必采用图形方式，可顶点 序列方式输出。(3) 根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调 用的情况，在主模块中调用上面两个子模块。2.2 任务定义根据课设题目要求，拟将整体程序分为三大模块。两个子模块相互独立，没有嵌套调 用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：(1) 建立有向图的存储结构。(2) 应用 Dijkstra 算法求出该有向图的最短路径。(3) 在 主 函 数 中 调 用 两 个 子 函 数 ， 完 成

7、最 短 路 径 的 程 序 设3算法设计3.1图的邻接矩阵的存储结构一个图的邻接矩阵表示唯一的。故在图的邻接矩阵表示中，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有 n个元素的一维数组存储顶点信息，其中下标为 i的元素存储顶点 vi的信息。本设计是基于类 C语言的 算法描述，因此，图的邻接矩阵的存储结构定义如下：#define MVNum 50typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum ；Mgraph;在本系统中，以邻接矩阵存储有向图，如图3.1a中有向图G所示，其邻接矩阵为图3.1

8、b所示：OOOO10OO30100OOOO5OOOOOOOOOOOO50OOOOOOOOOOOOOO10OOOOOO20OO60OOOOOOOOOOOO图3.1b G的邻接矩阵b3.2 Dijkstra 算法思想 （1）Dijkstra 算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。用自 然语言描述如下：初始化S和D,置空最短路径终点集，置初始的最短路径值；Sv1=TRUE;Dv1=0;While（S 集中的顶点数 arcsij=w图4.2 Create函数流程图4.3 Dijkstra函数流程图如图4.3所示接下一页i=m接上一页YSv=TRUEi=i+1接下一页图4.3 D

9、ijkstra 函数流程图5 源代码#include#include#define MVNum 50#define Maxint 1111typedef char VertexType; /typedef int Adjmatrix;typedef enum FALSE,TRUEboolean; typedef struct /VertexType vexsMVNum; /Adjmatrix arcsMVNumMVNum; / MGraph; / 定义邻接矩阵结构类型 void CreateMGraph(MGraph *G,int m,int n) 构造图 G int i,j,k,w;char

10、 a,b;for(i=1;ivexsi=i;for(i=1;i=m;i+) / for(j=1;jarcsij=Maxint;printf(” 输入d条边的i,j for(k=1;karcsij=w; /printf( 有向图的存储结构建立完成定义顶点图的邻接矩阵顶点向量 存放顶点的一维数组邻接矩阵二维数组采用数组(邻接矩阵)表示法，/构造顶点向量初始化邻接矩阵及 w:n,n);构造邻接矩阵输入一条边依附的顶点及权值弧的权值!n);printf(*n);void Dijkstra(MGraph G,int v1,int m)/用Dijkstra 算法求G中v1顶点到其余顶点v的最短路径pv及带

11、权长度Dv int DMVNum,PMVNum;int v,i,w,min;boolean SMVNum;/ S 以求得最短路径的终点的集合for(v=1;v=m;v+)Sv=FALSE;Dv=G.arcsv1v;if(DvMaxint)Pv=v1;elsePv=0;Dv1=0;Sv1=TRUE; / 初始化， v1 顶点属于 s 集/ 开始主循环，每次求得 v1 到某个 v 顶点的最短路径，并加 v 到 s 集 for(i=2;i=m;i+) / 其余 n-1 个顶点min=Maxint; / 当前所知离 v1 顶点的最近距离 for(w=1;w=m;w+)if(!Sw&Dwmin) / w

12、 顶点在 v-s 中v=w;min=Dw; /w 顶点离 v1 顶点更近Sv=TRUE;for(w=1;w=m;w+) / 更新当前最短路径及距离 if(!Sw&(Dv+G.arcsvwDw) /修改 Dw 和 Pw,w 属于 v-sDw=Dv+G.arcsvw;Pw=v;printf( 路径长度 路径 n);for(i=1;i=m;i+)printf(%5d,Di);printf(%12c,i-1+a);v=Pi;while(v!=0)printf(-%c,v-1+a); v=Pv;printf(n);void main()MGraph G;int m,n,v;char ch;printf(

13、 输入所需图的顶点个数和边数 m,n:);scanf(%d,%d,&m,&n);CreateMGraph(&G,m,n);while (v=m)printf( 求最短路径，请输入初始点 v:); fflush(stdin);scanf(%c,&ch);printf(n);v=ch-a+1;Dijkstra(G,v,m);6调试与测试6.1合法数据输入回(1 )合法数据测试结果如图6.1所示倫人所需團的顶点个数和边数叫戸恳厂A输入百築边的 iSw：11复 E 100即引30af Cj 10bj Cj 5Cj dj 50 fj 10 dj 20fj 0有冋團的存储结掏建立完成！求最短蹈去请输入初始

14、点审證路径长便一-路轻0a1111b10c_a50dl_8C_i30e_a00f-d-e-a求最短路径请输入初始点Mb路径11110b5c-bBEd-c-b1111e66求最短路径,请输入初始点祥|Ik1rC:Win do ws system 3 3Debugl,exe-1图6.1合法数据测试结果6.2非法数据输入(2)非法数据测试结果如图6.2所示i_i，二d owssystem 3 2De bu gl 启）嶽入所需團的顶点个数和边敷恥口: dT谕入条边的i. j及“：亀f100* Sj 30打 Cj 10bc., 5dj dj 50a, f, io dj 20&j f j 0有向图的存储結

15、枸建立芸成！4oMo|=4QM4=MG|QM=4=QUQ|QMcM43|Qk44=MQMc求最矩路径，请输入初始v：h路径长度-踣径弋5勢93460a-hJ Pres 也y k&y to cantinue,图6.2非法数据测试结果当前任务已达到任务目标，对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n),调整最短路径的循环共执行n-1次，所以，时间复杂度是O(n2)。采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O(n2)。总结本次课程设计涉及到的范围很广， 让我比较系统的对 C 语言和数据结构知识进行了一次 整理和复习。 本系统存在的问题主要是程序完成

16、后， 调试时没有发现问题， 但是当输入开始 节点后，运行框却不停的出现” -a ” ,后来重新检查程序时发现for 循环的括号后面多了一个“；”，去掉该分号之后，程序可以运行。在这次课程设计中我体会到C语言超强的逻辑性以及能够熟练使用 VC+编译环境的重要性，对C语言与数据结构这两门课程有了新的认识，它们既有联系， 又相互区别，在编写程序过程中要灵活应用。 我对数据结构的理解还有 待加强，这次课程设计应用的算法是 Dijkstra 算法。在学习的过程中自己对这方面的知识 比较生疏，所以在算法设计过程中比较困难，尤其是设计Dijkstra 算法的流程图时，发现自己对流程图这一块知识存在漏洞，有待加强。目前，该课设的缺点是：