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

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

单源点最短路径算法的实现
学生姓名学号班级成绩指导教师

数学与计算机科学学院
2015年1月2日

数据结构课程设计评阅书

题目单源点最短路径算法的实现学生姓名学号指导教师评语及成绩

成绩：教师签名：年月日教研室意见

总成绩：室主任签名：年月日

课程设计任务书
2014—2015学年第1学期
专业：学号：姓名：
课程设计名称：数据结构课程设计
设计题目：单源点最短路径算法的实现
完成期限：自2014年12月22日至2015年1月2日共2周
设计内容及要求:
最短路径问题已经被应用到GIS、GPS等信息管理系统中，为人们生活带来了很大便利。它属于图结构问题，其解决方法也有不少（如Dijkstra、A-star）。单源点最短路径问题解决的是既定起点的情况下，寻求该点到图中其它顶点的最短路径。请用C/C++语言的结构体、指针、数据结构等基础知识，编写程序实现图的结构定义、图的存储，以及求解单源点最短路径。
设计过程以及写作要求如下：
（1）要针对本题目，认真研究所设计的内容，用简明扼要的语言描述课题，给出课题的基本内容及要求；
（2）根据数据结构的相关知识给出实现建立任意m个顶点n条边的图算法、按照用户给定的源点和目标点，求出它们间的最短路径（打印出来）算法的基本策略及思路；
（3）给出较为详尽数据结构与算法，算法可以用流程图、伪代码等描述手段进行描述；
（4）给出一个完整的算法实现的C/C++程序，算法中的各子算法要力求用函数来实现；
（5）对编写的程序要进行详尽的测试分析；
（6）对本课题的设计工作要进行一个完整深刻的总结。
最终设计成果形式为：
设计软件一套；
撰写一份课程设计说明书一份，打印并装订成册。

指导教师（签字）：教研室主任（签字）：
批准日期：年月日
摘要

本系统以VC++作为软件开发环境，C语言作为程序开发语言，邻接矩阵作为存储结构，设计与实现了最短路径运算。该系统实现了有向图的存储、最短路径的运算等主要功能。依照该系统可以解决生活中许多问题，比如交通路线的选择，工程时间的预算等等，让人们可以做出合理的选择。本系统通过分析课题的背景、意义、要求，分别从课题描述、逻辑设计、算法设计、调试与测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。界面清晰，操作简单，易于用户接受。
关键词：VC++;邻接矩阵;最短路径

目录
TOC\o"1-3"\h\z\uHYPERLINK\l_Toc245951课题描述 PAGEREF_Toc245951
HYPERLINK\l_Toc221462问题分析与任务定义 PAGEREF_Toc221462
HYPERLINK\l_Toc306732.1问题分析 PAGEREF_Toc306732
HYPERLINK\l_Toc282232.2任务定义 PAGEREF_Toc282232
HYPERLINK\l_Toc8533算法设计 PAGEREF_Toc8533
HYPERLINK\l_Toc11893.1图的邻接矩阵的存储结构 PAGEREF_Toc11893
HYPERLINK\l_Toc4903.2Dijkstra算法思想 PAGEREF_Toc4904
HYPERLINK\l_Toc321754系统逻辑设计 PAGEREF_Toc321755
HYPERLINK\l_Toc25794.1主函数流程图如图4.1所示 PAGEREF_Toc25795
HYPERLINK\l_Toc57554.2Create函数流程图如图4.2所示 PAGEREF_Toc57556
HYPERLINK\l_Toc26824.3Dijkstra函数流程图如图4.3所示 PAGEREF_Toc26828
HYPERLINK\l_Toc64075源代码 PAGEREF_Toc640711
HYPERLINK\l_Toc192536调试与测试 PAGEREF_Toc1925314
HYPERLINK\l_Toc7286.1合法数据输入 PAGEREF_Toc72814
HYPERLINK\l_Toc313206.2非法数据输入 PAGEREF_Toc3132015
HYPERLINK\l_Toc24017总结 PAGEREF_Toc2401716
HYPERLINK\l_Toc9706参考文献 PAGEREF_Toc970617

1课题描述