宫恩超，李鲁群

(上海师范大学信息与机电工程学院，上海200234)

基于Bellman-Ford算法的动态最优路径算法设计

宫恩超，李鲁群

(上海师范大学信息与机电工程学院，上海200234)

针对动态变化交通流下的最优路径问题，提出基于Bellman-Ford算法的动态最优路径算法。并用试验与仿真说明该算法可以迅速完成动态最优路径的计算。结果显示，在处理该路段突发的交通堵塞状况时，该算法可以节约行驶权重百分比大约在30%～60%。

动态;Bellman-Ford算法;最优路径

一、引 言

GIS对空间最优路径分析主要基于Dijkstra算法，如ArcInfo中的Network采用二叉堆优先级队列来实现Dijkstra算法，GeoStar的网络分析采用快速排序的FIFO队列来实现Dijkstra算法。随着计算机网络、数据采集系统的技术进步，人们已经可以快捷地实时获取瞬息万变的动态交通路况信息，在这种情况下，实时进行空间分析规划动态最优路径已经成为当今亟待解决的问题之一。传统静态的Dijkstra算法已无法解决交通网络中的实时导航、通勤、调度等时刻变化的交通流量情况。针对该问题，本文提出基于Bellman-Ford算法的动态最优路径算法来实现动态交通流量下的最优路径计算。

二、国内外研究现状

目前针对动态最优路径问题的研究主要集中在两方面:①从算法本身分析并改进，力求在算法时间复杂度上不断取得突破;②对交通网络结构进行相应的预处理工作，例如将交通网络分层，高层次的网络是主干道，用主干道将整个网络分成多个自然网络。在路径查询时逐步削减初始图，即网络低层次的起点或终点总是向毗邻的高层次上溯。……