基于改进的Dijkstra算法的动态最短路计算方法

被引：45

作者：

刘建美 ^{[1
,2
]}

马寿峰 ^{[2
]}

马帅奇 ^{[1
]}

机构：

[1] 济宁学院数学系

[2] 天津大学系统工程研究所

来源：

系统工程理论与实践 | 2011年 / 06期

基金：

天津市科技支撑计划;

关键词：

最短路; 改进的Dijkstra算法; 速度; 超车;

D O I：

暂无

中图分类号：

U491 [交通工程与交通管理];

学科分类号：

082302 ; 082303 ;

摘要：

首先将所研究的时间段进行时段划分,然后基于每个路段在每个时段内的历史平均速度给出了改进的Dijkstra算法,它可以给出任意时刻从任意节点位置出发到达任一目的地的行程时间最短的路径及其相应的行程时间;其次在允许超车行为存在的条件下将出行者进行分类,并给出了相应的最短路算法.论文最后给出了相应的算例验证了算法的可行性.

引用

页码：1153 / 1157

页数：5

共 8 条

[1] Dijkstra的一种改进算法 [J].

孙强 ;

沈建华 ;

顾君忠 ;

不详 .

计算机工程与应用 , 2002, (03) :99-101

[2] 车辆导航系统的动态最优路径搜索方法研究 [J].

苏永云 ;

晏克非 ;

黄翔 ;

朱培康 .

系统工程, 2000, (04) :32-37

[3] Improved algorithm for all pairs shortest paths [J].

Han, YJ .

INFORMATION PROCESSING LETTERS, 2004, 91 (05) :245-250

[4] Shortest paths in a network with time-dependent flow speeds [J].

Sung, K ;

Bell, MGH ;

Seong, M ;

Park, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 121 (01) :32-39

[5] An 'all pairs shortest paths' distributed algorithm using 2n(2) messages [J].

Haldar, S .

JOURNAL OF ALGORITHMS, 1997, 24 (01) :20-36

[6] TIME DEPENDING SHORTEST-PATH PROBLEMS WITH APPLICATIONS TO RAILWAY NETWORKS [J].

NACHTIGALL, K .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1995, 83 (01) :154-166

[7] FIBONACCI HEAPS AND THEIR USES IN IMPROVED NETWORK OPTIMIZATION ALGORITHMS [J].

FREDMAN, ML ;

TARJAN, RE .

JOURNAL OF THE ACM, 1987, 34 (03) :596-615

[8]

A time-dependent shortest path algorithm for real-time intelligent vehicle /highway systems. Ziliaskopoulos A K,Mahmassani H S. Transportation Research . 1993

← 1 →