| 基于改进的Dijkstra算法的动态最短路计算方法 |
| |
| 引用本文： | 刘建美,马寿峰,马帅奇.基于改进的Dijkstra算法的动态最短路计算方法[J].系统工程理论与实践,2011,31(6):1153-1157. |
| |
| 作者姓名： | 刘建美 马寿峰 马帅奇 |
| |
| 作者单位： | 1. 济宁学院 数学系, 济宁 273100;2. 天津大学 系统工程研究所, 天津 300072 |
| |
| 基金项目： | 国家自然科学基金，天津市科技支撑计划重点项目 |
| |
| 摘 要： | 首先将所研究的时间段进行时段划分, 然后基于每个路段在每个时段内的历史平均速度给出了改进的Dijkstra算法, 它可以给出任意时刻从任意节点位置出发到达任一目的地的行程时间最短的路径及其相应的行程时间; 其次在允许超车行为存在 的条件下将出行者进行分类, 并给出了相应的最短路算法. 论文最后给出了相应的算例验证了算法的可行性.
|
| 关 键 词： | 最短路 改进的Dijkstra算法 速度 超车 |
| 收稿时间： | 2009-8-31 |
Computation method of the dynamic shortest path based on improved-Dijkstra algorithm |
| |
| LIU Jian-mei,MA Shou-feng,MA Shuai-qi.Computation method of the dynamic shortest path based on improved-Dijkstra algorithm[J].Systems Engineering —Theory & Practice,2011,31(6):1153-1157. |
| |
| Authors: | LIU Jian-mei MA Shou-feng MA Shuai-qi |
| |
| Institution: | 1. Department of Mathematics, Jining College, Jining 273100, China;2. Institute of Systems Engineering, Tianjin University, Tianjin 300072, China |
| |
| Abstract: | 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 pr... |
| |
| Keywords: | shortest paths improved-Dijkstra algorithm speed pattern passing property |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《系统工程理论与实践》浏览原始摘要信息 |
| 点击此处可从《系统工程理论与实践》下载免费的PDF全文 |
