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

Computation method of the dynamic shortest path based on improved-Dijkstra algorithm

作　　者：刘建美[1,2] 马寿峰[2] 马帅奇[1] 

机构地区：[1]济宁学院数学系,济宁273100 [2]天津大学系统工程研究所,天津300072

出　　处：《系统工程理论与实践》2011年第6期1153-1157,共5页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70671073);天津市科技支撑计划重点项目(08ZCKFSF01000)

摘　　要：首先将所研究的时间段进行时段划分,然后基于每个路段在每个时段内的历史平均速度给出了改进的Dijkstra算法,它可以给出任意时刻从任意节点位置出发到达任一目的地的行程时间最短的路径及其相应的行程时间;其次在允许超车行为存在的条件下将出行者进行分类,并给出了相应的最短路算法.论文最后给出了相应的算例验证了算法的可行性.Firstly,the paper divides the working hours into several time intervals and defines some different speed patterns based on historical data.Then one improved-Dijkstra algorithm with non-passing property is suggested,which can compute the paths with the shortest traveling time from any single-source node to all the other nodes.Sequentially,we divide travelers into three types which imply the existence of passing behavior,and the corresponding shortest paths algorithm is given.Finally,numerical examples are presented to validate the feasibility and efficiency of the preceding algorithm.

关 键 词：最短路 改进的Dijkstra算法 速度 超车 

分 类 号：U491[交通运输工程—交通运输规划与管理]