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

《单源点最短路径算法的实现_____数据结构_课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计设计说明书单源点最短路径算法的实现学生姓名学号班级成绩指导教师数学与计算机科学学院2014年3月7日课程设计任务书2013—2014学年第2学期专业：学号：姓名：课程设计名称：数据结构课程设计设计题目：单源点最短路径算法的实现完成期限：自2014年2月24日至2014年3月7日共2周设计依据、要求及主要内容（可另加附页）：最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径（特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。在加入时可以记录每个顶点的

2、最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题，这对以上几个问题采用了迪杰斯特拉算法。并为本系统设置一人性化的系统提示菜单，方便使用者的使用。本课程设计中主要完成以下内容：1.建立图的存储结构。2.解决单源最短路径问题。3.实现两个顶点之间的最短路径问题。基本要求如下：1.程序设计界面友好；2.设计思想阐述清晰；3.算法流程图正确；4.软件测试方案合理、有效。指导教师（签字）：教研室负责人（签字）：批准日期：年月日评语：指导老师签名：年月日课程设计评阅摘要

3、本软件以VC++作为开发平台，设计了关于从某个单一原点到任意顶点的一个类似于查询，咨询系统的软件。它能够准确快速的计算出从某个单一原点到任意顶点的最短路径以及路径长度。该类软件目前广泛运用于城市交通运输系统，为人们出行带来了方便。关键字：VC++；最短路径；迪杰斯特拉算法；目录目录-1-1、课题描述-1-2、问题分析与设计思想-2-3、概要设计-4-4、详细设计-6-4.1建立图的存储结构-6-4.2单源最短路径-6-5、程序编码-8-6、程序调试和测试-12-7、总结-16-参考文献-16-1、课题描述在城市交通网络日益发达的今天，针对人们出行关心的各种问题，利用计算机软件建立一个交通咨询系

4、统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边表示各个城市之间的交通关系，所带权值为两个城市间的距离。-15-2、问题分析与设计思想问题分析：可以将该系统大致分为两个部分：①　建立网络图的存储结构：定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。②　解决单源最短路径问题：单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。设计思想：Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法。首先，引进一个辅助向量D，它的每个分量D[i]表示当前所找到的从源点v到每个终点vi的最短路径长度。它的初始状态为：若v到vi

5、有弧，则D[i]为弧上的权值，否则D[i]为无穷大。显然，长度为:D[j]=Min{D[i]

6、vi属于V} 的路径就是从v出发的长度最短的一条路径。此路径为(v,vi)。那么，长度次短的路径是哪一条呢？假设该次短路径的终点是vk，则可以证明，这条路径或者是(v,vk)，或者是(v,vj,vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。-15-N设定变量，初始化dist[]数组，使其与cost[V0][i]相对应定义顶点V0与自身的距离为0;定义经过的顶点个数为0；定义顶点集合S[MAX]初始化数组S[i]，并规定i为顶点序号将起点V0加入数组首先初始

7、最短路径mindis为无穷大；查找离顶点V0最近的顶点，并赋值距离给mindis=dist[j];根据找到的顶点寻找下一个路径最短的顶点S[u]，并记录最短路径dis=dist[u]+cost[j]；dis是否大于V0直接到S[u]的距离；最短路径为dist记录经过的顶点;j为寻找下一个顶点的变量添加顶点到最短路径当中；输出顶点V0到各个顶点的最短路径结束图2.1Dijkstra算法流程图-15-3、概要设计存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递

8、增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，假设存在G=，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使