约束最短路径问题分析及算法研究.doc

摘要:近年来，路径寻优问题成为学术界研究的一个热点问题。其中，约束最短路径问题得到了人们越来越多的关注。本文主要研究了一类对于具有禁止通行限制信息的交通网络问题，即节点带有约束的最短路径问题。由于最短路径的求解是有后效性的，因此很多经典的求解最短路径的算法不能直接用来求解该问题。本文给出一种求解结点有约束的交通网络最短路径建模方法。该方法可以把节点有约束的网络问题转化为另外一个节点无约束的一般网络模型, 之后就可用任一传统高效的算法求其最短路径, 从根本上降低了问题的复杂性, 为很好地解决交通、通信等领域中的此类问题提供了有益的方法。

第一章主要介绍了约束最短路径问题的研究背景以及研究现状。第二章简单介绍了什么是最短路径问题，具体有哪些形式的最短路径问题和最短路径问题的经典求解方法。第三章例举了一个无约束的最短路径问题，且用经典的Dijkstra算法求解了该问题，给出了具体的计算步骤。第四章例举了一个节点有约束的交通网络问题，详细描述了如何通过建立模型的方法把该问题转化为一个节点无约束的最短路径问题。并用经典方法求解了最短路径问题。

关键词：交通网络；约束最短路径；Dijkstra算法

目录

摘要

Abstract

1 绪论（引言）-2

1.1 研究背景-2

1.2 国内外现状-3

2 最短路径问题-5

2.1 最短路径问题的定义-5

2.2 最短路径的形式-5

2.3 最短路径问题的求解方法-5

2.4 本文研究主要问题-6

3 无约束节点的最短路径模型-7

3.1 Dijkstra算法流程-7

3.2 Dijkstra算法计算步骤-8

3.3 结果分析-9

4 结点有约束的交通网络最短路径-10

4.1 问题及模型-10

4.2 最短路径网络模型-11

4.3 应用举例-12

4.4 结论-15

结    论-16

参 考 文 献-17

致    谢-19