交通网络最短路径算法分析与研究.doc

摘要:交通网络与我们的日常生活息息相关，密不可分。而交通网络问题中的一个热点问题就是最短路径问题。目前在交通领域，随着我们生活节奏的加快，各种形式的交通工具在不断增加，交通网络的建设也在不断推进，以至于交通网络越来越发达，也越来越复杂。今天的人们在出行时不仅关心出行的费用，也越来越关心出行的时效。所以相应地，在这方面的科学研究领域，关于最短路径算法的研究和应用也越来越多。

首先，本文在第一章引言部分简单介绍了交通网络问题的重要性及解决最短路径问题的几个常用方法。然后在第二章简要介绍了研究最短路径所需要的图论知识。第三章就我们所关注的最短路径问题给出了详细的分析及描述。解决最短路径问题的算法非常丰富，本文利用几种常见的最短路径算法对实例进行了分析、研究和实现。在接下来的三章，本文讨论了几种算法的思想、原理和实现方法。分别用最经典的Dijkstra算法、Warshall-Floyd算法，还包括启发式算法—遗传算法来求解了最短路径问题。在第七章，我们把三种算法进行了比较，评价了它们的优点和缺点，以便未来更好的地运用它们解决实际的交通网络问题。

关键词：交通网络；最短路径；Dijkstra算法；Warshall-Floyd算法；遗传算法

目录

摘要

Abstract

1 引言-1

2 图论基础-3

2.1 图的一些基本概念和属性-3

2.2 树图和最小生成树-3

2.2.1 树的定义及性质-3

2.2.2 图的生成树-4

2.3 图的搜索策略-4

2.3.1 深度优先搜索算法-4

2.3.2 广度优先搜索算法-5

2.3.2 启发式搜索算法-5

2.4 最小生成树及Prim算法-6

2.4.1 最小生成树-6

2.4.2 最小生成树的算法：Prim算法-6

3 交通网络中的最短路径问题-7

3.1 问题描述-7

3.2 最短路径算法分类体系-7

3.2.1问题类型-7

3.2网络特征-8

3.3 实现技术-9

4 Dijkstra算法-10

4.1 基本思想-10

4.2 基本步骤-10

5 Warshall-Floyd算法-11

5.1 算法思想-11

5.2 算法步骤-11

6 遗传算法-12

6.1 遗传算法的基本操作-12

6.1.1 选择-12

6.1.2 交叉-13

6.1.3 变异-13

6.2算法步骤-14

7 最短路径算法的分析比较-15

7.1 Dijkstra算法-15

7.2 Warshall-Floyd算法-15

7.3 遗传算法-15

8.最短路径算法的应用-17

8.1 Dijkstra求解实际问题-17

8.2 Floyd算法求解实际问题-19

8.3 遗传算法求解实际问题-21

结论-23

参考文献-24

附录A Dijkstra算法程序-25

附录B Floyd算法程序-29

附录C 遗传算法程序-31

致谢-45