图中最短路径的算法求解.doc

摘要:随着人们生活水平的提高，外出旅行已越来越普遍。有效的计算出城市各个景点的最短路径，缩短路途花费的时间来为旅行提供便捷的服务显得尤为重要。 

本文研究如何在旅游地图中应用最短路径来搜索到便捷有效的旅游路线，应用Dijkstra算法来为从任何一个源点找到与其它各点的最短距离，并且编写出C++程序算法来实现最短路径的求解，给出实际算例和实验数据，验证Dijkstra算法的普遍性。

关键词：最短路径   Dijkstra算法   C++

目录

摘要

Abstract

1 绪论-1

1.1 图论的基本概念1

1.2 图的存储结构-2

2 最短路径问题-3

2.1 最短路径-3

3 应用举例-6

3.1 Dijkstra算法在旅游景点中的应用6

4 结论11

参考文献12

致谢13