中南大学
《数据结构》课程设计
题 目 第9题 Dijkstra算法求最短路径
学生姓名 XXXX 指导教师 XXXX
学 院 信息科学与工程学院 专业班级 XXXXXXX
完成时间 XXXXXXX
1
目录
第一章 问题分析与任务定义---------------------------------------------------------------------3 1.1 课程设计题目-----------------------------------------------------------------------------3 1.2 原始数据的输入格式--------------------------------------------------------------------3 1.3 实现功能-----------------------------------------------------------------------------------3 1.4 测试用例-----------------------------------------------------------------------------------3 1.5 问题分析-----------------------------------------------------------------------------------3 第二章 数据结构的选择和概要设计------------------------------------------------------------4 2.1 数据结构的选择--------------------------------------------------------------------------4 2.2 概要设计-----------------------------------------------------------------------------------4 第三章 详细设计与编码-----------------------------------------------------------------------------6 3.1 框架的建立---------------------------------------------------------------------------------6 3.2 点结构体的定义---------------------------------------------------------------------------7 3.3 创立带权值有向图------------------------------------------------------------------------8 3.4 邻接矩阵的显示---------------------------------------------------------------------------9 3.5 递归函数的应用---------------------------------------------------------------------------10 3.6 Dijkstra算法实现最短路径--------------------------------------------------------------10 第四章 上机调试------------------------------------------------------------------------------------11 4.1 记录调试过程中错误和问题的处理---------------------------------------------------11 4.2 算法的时间课空间性能分析------------------------------------------------------------11 4.3 算法的设计、调试经验和体会---------------------------------------------------------11 第五章 测试结果-----------------------------------------------------------------------------------12 第六章 学习心得体会-----------------------------------------------------------------------------12 第七章 参考文献-----------------------------------------------------------------------------------12 附录------------------------------------------------------------------------------------------------------12
2
第一章 问题分析与任务定义
1、课程设计题目：
1.1题目：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法，寻找和输出带权有向图中某个源点到其余各点的最短路径
1.2要求：采用适当的存储结构实现带权有向图的存储，建立，输入、显示，以及使用Dijkstra算法。
1.3具体任务：建立图的存储模块，建立图的输出模块，在建图后从单源点开始求最短路径，并显示出来。
2.原始数据的输入格式
2.1建图：2.1.1数字
2.2显示：2.2.1数字+逗号+数字+回车
2.2.2字母+回车
3.实现功能
3.1建立有向图
3.2显示存储的有向图
3.3显示从顶点到其他各个顶点的最短路径和是否存在路径
4.测试用例
4.1正确数据：输入顶点；边值信息
输出结果：最短路径是否存在，存在的情况最短路径是多少，其次是不存在。
5.问题分析
实现本程序要解决以下几个问题：
5.1如何存储一个有向图。
5.2如何在界面中输出该有向图。 5.3如何定义起始源点。 5.4如何选择出最短路径。
5.5找到的最短路径如何输出。
3
第二章 数据结构的选择和概要设计
1.数据结构的选择：
在图的结构中，任意两个顶点之间都可能存在关系，比线性表和树要复
杂。由于不存在严格的前后顺序，因而不能采用简单的数组来存储图;另一方面，如果采用链表，由于图中各顶点的度数不尽相同，最小度数和最大度数可能相差很大，如果按最大度数的顶点来设计链表的指针域，则会浪费很多存储单元，反之，如果按照各个顶点设计不同的链表结点，则会给操作带来很大的困难。
在此我选用邻接矩阵的存储结构。采用邻接矩阵存储，很容易判断图中两个顶点是否相连，也容易求出各个顶点的度。不过任何事情都不是完美的，采用邻接矩阵存储图时，测试其边的数目，必须检查边二维数组的所有元素，
2
时间复杂度为O（n）,这对于顶点很多而边较少的图（稀疏图）是非常不合算的。
以邻接矩阵存储有向图。
2.概要设计
2.1对于最短路径问题：
最短路径是在实际应用中非常有用的工具，我们常见的两种最短路径是：
（1）从某源点到其余各顶点之间的最短路径。 （2）每一段顶点之间的最短路径
在这里我们解决第一类问题。 2.2 Dijkstra算法用于求最短路径：
Dijkstra算法是按路径长度递增的次序逐步产生源点到其他顶点间的最短路径。算法建立一个顶点集合S，初始时该集合只有源点V0，然后逐步将已求得最短路径的顶点加入到集合中，直到全部顶点都在集合S中，算法结束。
2..3 Dijkstra算法思想
设cost[i,j]=0，S为已经求得最短路径的顶点集合，distance[i]数组的每个元素表示当前状态下源点V0到Vi的最短路径。算法如下： 1) 初始化：S={V0}, distance[i]=cost[0,i]。
2) 选择一个终点Vj，满足distance[j]=MIN{ distance[i]|Vi∈V-S}。 3）把Vj加入到S中。
4）修改distance数组元素，修改逻辑为对于所有不在S中的顶点Vi.
if(distance[j]+cost[i,j]< distance[i]) { distance[i]=
4
distance[j] ]+cost[i,j] }
5)重复操作2）、3）、4），直到全部顶点加入到S中。 2.4 实现流程
在任意图中实现求最短路径问题，第一步是要能成功的在内存中输入图的信息，图的信息有两个，一是顶点个数，二是每两点之间的权值信息。当建立图之后，对图进行遍历才能使用Dijkstra算法求出最短路径；在完成了图的建立之后，用Dijkstra算法的思想，从单源点开始，求出到各个顶点的最短路径，并能够实现显示功能。 程序流程图：
开始 输入顶点边个数 输入顶点名称 输入每条边的信息 创建图 返回每个结点 的位置 Dijkstra算法的实现 D[w]