最短路径算法问题.doc

最短路径算法问题
页数 31 字数 11419

摘 要
最短路径算法问题是计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。传统的最短路径算法主要有Floyd算法和Dijkstra算法。Floyd算法用于计算所有节点之间的最短路径。Dijkstra算法则用于计算一个节点到其他所有节点的最短路径。Dijkstra算法是已经证明的能得出最短路径的最优解，但它的效率是一个很大的问题。对于具有n个节点的一个图，计算一个节点到图中其余节点最短路径的算法时间复杂度为O(n2)。对于一座大中型城市，地理节点数目可能达到几万个到几十万个，计算最短路径的时间开销将是非常巨大的。
本文根据吴一民老师的建议，分析当前存在的各种求最短路径的算法，提出一种新的基于层次图的最短路径算法，即将一个平面图划分若干子图，子图抽象为一个高层图。最短路径的计算首先在高层图中进行，缩小了最短路径的查找范围，降低了最短路径计算的时间开销。由于可以动态计算子图间的阻抗函数，算法可适用于动态交通诱导系统。


关键词 最短路径，层次图模型，Dijkstra算法




ABSTRACT
This paper discusses a new algorithm for the shortest path founding based on hierarchical graphs. It plots out a flat graph into some sub-graphs, which are abstracted as a high-level graph. The calculation for the shortest path founding begins at the high-level graph. This method shrinks the searching range of the shortest path and reduces the time spending of calculating it. Since the impedance function among sub-graphs can be calculated dynamically, this algorithm can be applied to dynamic traffic inducement system.

Index Terms: shortest path, hierarchical graph, Dijkstra algorithm