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

1、数据结构课程设计设计说明书单源点最短路径算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2015年 1 月 2 日 数据结构 课程设计评阅书题 目单源点最短路径算法的实现学生姓名学 号指导教师评语及成绩成 绩： 教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日课程设计任务书20142015学年第1学期专业： 学号： 姓名： 课程设计名称： 数据结构课程设计 设 计 题 目： 单源点最短路径算法的实现 完 成 期 限：自 2014 年 12 月 22 日至 2015 年 1 月 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 调试与测试146.1合法

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

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

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

8、f550图3.1a 有向图G图3.1b G的邻接矩阵 10 30 100 5 50 10 20 60 图3.1b G的邻接矩阵图3.1a 有向图G505feabcd1006030 2010103.2 Dijkstra算法思想（1）Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。用自然语言描述如下：初始化S和D,置空最短路 径终点集，置初始的最短路径值；Sv1=TRUE;Dv1=0;While(S集中的顶点数<n) 开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中; Sv=TRUE; 更新当前最短路径及距离。（2）Dijkstra算法结束后，通过

9、设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。4 系统逻辑设计4.1 主函数流程图如图4.1所示开始输入顶点个数和边数m,n开始输入数据调用Create函数建立图的邻接矩阵调用Create函数N调用Dijkstra函数Y3.1主函数流程图请输入初始点v4.2 Create函数流程图调用Dijkstra函数求得最短路径k=1 结束图4.1 主函数流程图4.2 Create函数流程图如图4.2所示开始定义顶点序号i=1，顶点数m,边数nNi<=mY存入一维向量G.vexsi=ii=i+1i=1Ni<=mYi=i+1j=1Nj<=mY 10 30 100

10、5 50 10 20 60 对邻接矩阵m*m个单元初始化G.arcsij=Maxintj=j+1接下一页接上一页 N变量k=1k<=nY定位i,ji=a-a+1 , j=b-a+1G->arcsij=w给邻接矩阵有关单元赋权值wG.arcsij=wk=k+1 结束图4.2 Create函数流程图4.3 Dijkstra函数流程图如图4.3所示 开始定义G中v1到其余顶点v的最短路径、带权长度及最短路径终点的集合int DMVNum, PMVNum boolean SMVNum 定义顶点数 int mv=1Nv<=mY置空S Sv=FALSE Dv=G.arcsv1vN若权值小

11、于最大值 无穷Dv<MaxintYPv=0Pv=v1v=v+1初始化，v1顶点属于s集Dv1=0;Sv1=TRUE 开始主循环，每次求得v1到某个v顶点的最短路径，并加v到s集i=2接下一页接上一页Ni<=mmmmY当前所知离v1顶点的最近距离min=Maxint 顶点变量w=1Nw<=m、YN!Sw&&Dw<minYv=w W顶点离v1更近min=D wSv=TRUEw=w+1w=1Nw<=mYSv=TRUEN!Sw&&Dv+G.arcsvw<DwY修改Dw,Pw Dw=Dv+G.arcsvwPw=vw=w+1i=i+1接下

12、一页接上一页、i=1Ni<=mmmmY输出数据pvi=i+1结束图4.3 Dijkstra函数流程图 5 源代码#include<stdio.h>#include<stdlib.h>#define MVNum 50#define Maxint 1111typedef char VertexType; / 定义顶点typedef int Adjmatrix; typedef enum FALSE,TRUEboolean;typedef struct / 图的邻接矩阵VertexType vexsMVNum; /顶点向量 存放顶点的一维数组Adjmatrix arcs

13、MVNumMVNum; / 邻接矩阵二维数组MGraph; /定义邻接矩阵结构类型void CreateMGraph(MGraph *G,int m,int n) / 采用数组（邻接矩阵）表示法，构造图Gint i,j,k,w;char a,b;for(i=1;i<=m;i+) /构造顶点向量G->vexsi=i;for(i=1;i<=m;i+) /初始化邻接矩阵for(j=1;j<=m;j+)G->arcsij=Maxint;printf("输入%d条边的i,j及w:n",n);for(k=1;k<=n;k+) / 构造邻接矩阵fflu

14、sh(stdin);scanf("%c,%c,%d",&a,&b,&w); /输入一条边依附的顶点及权值i=a-'a'+1;j=b-'a'+1; G->arcsij=w; /弧<i,j>的权值printf("有向图的存储结构建立完成!n");printf("*n"); void Dijkstra(MGraph G,int v1,int m)/用Dijkstra算法求G中v1顶点到其余顶点v的最短路径pv及带权长度Dvint DMVNum,PMVNum;int v

15、,i,w,min;boolean SMVNum;/ S以求得最短路径的终点的集合for(v=1;v<=m;v+)Sv=FALSE;Dv=G.arcsv1v;if(Dv<Maxint)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&&Dw<min) / w顶点在v-s中v=w;min=Dw; /

16、w顶点离v1顶点更近Sv=TRUE;for(w=1;w<=m;w+) /更新当前最短路径及距离if(!Sw&&(Dv+G.arcsvw<Dw) / 修改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

17、=Pv;printf("n"); void main() MGraph G;int m,n,v;char ch;printf("输入所需图的顶点个数和边数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

18、9;+1;Dijkstra(G,v,m); 6 调试与测试6.1合法数据输入（1）合法数据测试结果如图6.1所示图6.1合法数据测试结果6.2非法数据输入（2）非法数据测试结果如图6.2所示图6.2非法数据测试结果当前任务已达到任务目标，对于n个顶点的有向图，求一个顶点到其他顶点的最短路径的时间为O(n)，调整最短路径的循环共执行n-1次，所以，时间复杂度是O（n2）。采用邻接矩阵存储有向图，应处理每两个顶点之间的关系，所以空间复杂度为O（n2）。总结本次课程设计涉及到的范围很广，让我比较系统的对C语言和数据结构知识进行了一次整理和复习。本系统存在的问题主要是程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停的出现”<-a”,后来重新检查程序时发现for循环的括号后面多了一个“;”，去掉该分号之后，程序可以运行。在这次课程设计中我体会到C语言超强的逻辑性以及能够熟练使用VC+编译环境的重要性，对C语言与数据结构这两门课程有了新的认识，它们既有联系，又相互区别，在编写程序过程中要灵活应用。我对数据结构的理解还有待加强，这次课程设计应用的算法是Dijkstra算法。在学习的过程中自己对这方面的知识比较生疏，所以在算法设计过程中比较困难，尤其是设计Dij