单源点最短路径算法的实现(word文档良心出品).doc

数据结构课程设计
设计说明书

单源点最短路径算法的实现

学生姓名潘飞学号1221024012班级信管1201班成绩指导教师余冬梅

数学与计算机科学学院
2014年3月7日

课程设计任务书
2013—2014学年第2学期
专业：信息管理与信息系统学号：1221024030姓名：潘飞
课程设计名称：数据结构课程设计
设计题目：单源点最短路径算法的实现
完成期限：自2014年2月24日至2014年3月7日共2周
设计依据、要求及主要内容（可另加附页）：
最短路径算法关键先把已知最短路径顶点集（只有一个源点）和未知的顶点分开，然后依次把未知集合的顶点按照最短路径（特别强调一下是源点到该顶点的路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚）加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。针对最短路径问题，在本系统中采用图的相关知识，以解决在实际情况中的最短路径问题，本系统中包括了建立图的存储结构、单源最短问题，这对以上几个问题采用了迪杰斯特拉算法。并为本系统设置一人性化的系统提示菜单，方便使用者的使用。
本课程设计中主要完成以下内容：
1.建立图的存储结构。
2.解决单源最短路径问题。
3.实现两个顶点之间的最短路径问题。
基本要求如下：
1.程序设计界面友好；
2.设计思想阐述清晰；
3.算法流程图正确；
4.软件测试方案合理、有效。

指导教师（签字）：教研室负责人（签字）：

批准日期：年月日
评语：

指导老师签名：
年月日课程设计评阅

摘要

本软件以VC++作为开发平台，设计了关于从某个单一原点到任意顶点的一个类似于

查询，咨询系统的软件。它能够准确快速的计算出从某个单一原点到任意顶点的最短路径以

及路径长度。该类软件目前广泛运用于城市交通运输系统，为人们出行带来了方便。

关键字：VC++；最短路径；迪杰斯特拉算法；

目录
TOC\o"1-2"\h\uHYPERLINK\l_Toc3260目录 PAGEREF_Toc3260-1-
HYPERLINK\l_Toc2171、课题描述 PAGEREF_Toc217-1-
HYPERLINK\l_Toc296382、问题分析与设计思想 PAGEREF_Toc29638-2-
HYPERLINK\l_Toc198513、概要设计 PAGEREF_Toc19851-4-
HYPERLINK\l_Toc277704、详细设计 PAGEREF_Toc27770-6-
HYPERLINK\l_Toc32044.1建立图的存储结构 PAGEREF_Toc3204-6-
HYPERLINK\l_Toc208284.2单源最短路径 PAGEREF_Toc20828-6-
HYPERLINK\l_Toc300855、程序编码 PAGEREF_Toc30085-8-
HYPERLINK\l_Toc260986、程序调试和测试 PAGEREF_Toc26098-12-
HYPERLINK\l_Toc252307、总结 PAGEREF_Toc25230-16-
HYPERLINK\l_Toc22059参考文献 PAGEREF_Toc22059-16-


PAGE\*MERGEFORMAT-15-

1、课题描述

在城市交通网络日益发达的今天，针对人们出行关心的各种问题，利用计算机软件建

立一个交通咨询系统。在系统中采用图来构造各个城市之间的联系，图中顶点表示城市，边

表示各个城市之间的交通关系，所带权值为两个城市间的距离。

2、问题分析与设计思想

问题分析：
可以将该系统大致分为两个部分：
①建立网络图的存储结构：
定义交通图的存储结构。邻接矩阵是表示图形中顶点之间相邻关系的矩阵。
②解决单源最短路径问题：
单源最短路径问题：已知有向图(带权)，期望找出从某个源点S∈V到G中其余各顶点的最短路径。

设计思想：
Dijkstra提出了一个按路径长度递增的次序产生最短路径的算法。首先，引进一个辅助
向量D，它的每个分量D[i]表示当前所找到的从源点v到每个终点vi的最短路径长度。
它的初始状态为：若v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。显然，
长度为:D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条路径。此路