几种求解最优路径的方法研究.docx

摘要:以最短路径研究为主的最优路径算法研究可以广泛地应用在计算机、信息科学、建筑学、地理学以及生物学等科学和实践领域。本文首先介绍了最短路径的国内外研究情况，对国内外一些相关研究进行了综合评述，详细介绍了五种常用的最短路径算法，包括Dijkstra算法、Warshall- Floyd算法、动态规划算法、A*算法和BFM算法；并简要阐述了最短路径的相关概念，最短路径的应用及分类；然后提出一个最短路径的问题(求解交通网络图的最短路径)并运用三种经典方法分别求解最短路径；且对结果进行对比分析得出几种求解最短路径方法的优劣；最后对文章进行了总结。

关键词：最短路径、Dijkstra算法、Floyd算法、动态规划算法

目录

摘要

Abstract

第一章  绪论-6

1.1研究背景和意义-6

1.2国内外研究现状-7

1）Dijkstra算法-8

1.1）基本思想-8

1.2）基本步骤-8

1.3）时间复杂度-9

2）  Warshall-Floyd算法-9

2.1）算法思想-9

2.2）时间复杂度-10

3） 动态规划求解最短路径-10

3.1）基本思想-10

3.2）动态规划基本步骤-10

4  A*算法-11

4.1）算法思想-11

4.2）搜索步骤-11

5） BFM算法-12

1.3研究内容和论文结构-12

第二章 最短路径算法概述-13

2.1最短路径的定义-13

2.2最短路径问题的应用-13

2.3最短路径问题的分类-13

第三章 问题提出和算法求解-15

3.1 问题提出-15

3.2 Dijkstra算法计算步骤及结果-15

3.2.1标号法求解-15

3.2.2迭代求解-16

3.3 Warshall-Floyd算法求解-18

3.4 动态规划算法求解-20

第四章 比较分析-23

4.1 Dijkstra算法的优劣-23

4.2 Warshall-Floyd算法的优劣-23

4.3动态规划算法的优劣-23

第五章 总结-24

参考文献-25

致谢-27