单源点最短路径算法的实现(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_Toc3008