摘要最短路径算法是计算机科学与运筹学中比较重要的一个部分，经典的最短路径算法有两种——Dijkstra算法和Floyd算法。本文主要讲解了图的基本定义以及详细阐述了最短路径算法，并且运用了 Dijkstra 算法来求解一个 24 点交通图的最短路径问题。本文以 C++为程序设计软件，为程序针对的用户提供了三种模式的最短路径求解：时间最短路径求解，路程最短路径求解以及换乘最短路径模式。本文还设计出了管理员模式，以供管理员针对交通图的实际情况进行对图的邻接矩阵的修改。作者最终完成了程序的设计以及仿真，并且在最后对程序的可行性进行了讨论。 22417
毕业论文关键词 最短路径 图论 数据结构 Dijkstra 算法
Title A study the shortest path algorithm AND The program design
Abstract
The shortest path algorithm is a quite important part of Computer Science
and Operations Research . There are two classic shortest path algorithm,
one is Dijkstra algorithm and the other one is Floyd algorithm. In this
paper, we explain the basic definition of Graph and the shortest path
algorithm in detail. We use Dijkstra algorithm to solve the shortest path
problem of a 24 road map. In this paper,we design the program based on C++.We
provide three models to find the shortest path for the users,who are the
program is designed for.There are finding the path which takes the
shortest time,finding the path which takes the shortest way and finding
the path which takes the minimum number of public transport
transferring .We design the administrator mode in this paper.This mode is
designed for an administrator to change the adjacency matrix with the
actual situation of traffic map. The author finally complete the design
and simulation of the program, and the feasibility of the program are
discussed in the end.
Keywords Shortest path Graph Data structure Dijkstra Algorithm
目 次
1 绪论 1
1.1 本文研究的内容目的和意义 1
1.2 国内外发展现状和趋势 2
1.3 本文主要完成的工作 3
1.4 章节安排 4
2 图与最短路径 5
2.1 图的基本概念 5
2.2 最短路径问题 8
2.3 总结与分析 14
3 应用实例 15
3.1 图的邻接矩阵 16
3.2 最短路径算法 17
3.3 输出算法 21
3.4 主体算法模块 22
3.5 程序运行结果 24
3.6 总结与分析 32
结论 33
致谢 34
参考文献35
1. 绪论
1.1 本文研究的内容目的和意义
随着我国经济建设的快速发展，城市交通供求矛盾也日益突出。城市交通网络的
扩大，在给乘客带来极大方便的时候，也给乘客选择合适的出行乘车路线带来了困惑。
因此我们需要通过最短路径算法设计出满足人们各项出行要求的合理化路线。在已有
城市交通条件下，设计合理的出行路径有助于人们选择出行时间，出行路线和公交换
乘方案等。出行最短路径选择实质上是研究交通网上的线路分布以及权值之和，即研
究乘客给出起点和终点后，如何自动的生成最优的出行路径方案。 C++最短路径算法研究和程序设计:http://www.youerw.com/zidonghua/lunwen_15037.html