解最短路径问题的两种方法及其应用.doc

摘要:图论是数学的一个分支，它以图为研究对象，研究由顶点和边组成的图形的数学理论和方法。最短路径问题是图论研究中的一个经典问题，在日常生活中有着重要的作用。例如，如果我们需要往返A地区和B地区之间，我们最希望知道的是从A地区到B地区间的众多路径中，哪一条路径的路途最短。最短路径问题旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。Dijkstra算法和动态规划方法则是解决最短路径的最常用的两种方法。Dijkstra算法是最有代表性的最短路径算法，在很多学科中都有详细的介绍，如数据结构、运筹学等等。而动态规划方法则是把一个问题分解为若干个子问题来求解最优解，在文献[1][2]中对这两种方法给出了详细的介绍。在实际生产生活中经常会遇到一类问题，如交通运输、旅游路线、管道铺设等，由于这些问题可以通过图形形象地进行说明，而且最短路径问题中边的权值往往可以从距离引申为其他沿路径线性积累的度量如时间、花费等。所以这些问题往往都可以转化为图论中的最短路径问题进行解决，文献[4][10]就考虑了如何用最短路径问题来解决一些实际问题。本文首先介绍了求解最短路径问题的Dijkstra算法和动态规划方法的基本思想及步骤，并通过一些具体的实际问题的求解来进一步明确最短路径问题的应用价值，同时通过这些实际问题的求解过程来进一步说明这两种方法的求解过程及各自的特点。

关键词  最短路径；Dijkstra算法；动态规划；单源最短路径；多源最短路径

目录

摘要

Abstract

1 绪论-1

2 最短路径的两种解法-3

2.1 Dijkstra算法-3

2.1.1 基本介绍-3

2.1.2 算法思路-3

2.1.3 实例说明-4

2.2 动态规划-5

2.2.1 基本介绍-5

2.2.2 基本思想-5

2.2.3 建模过程-6

2.2.4 实例说明-6

2.2.5 多源最短路径-8

3 应用实例-10

结论-19

致谢-20

参考文献-21

附录-22