| 动态速度和代价约束的最短路径算法 |
| |
| 引用本文： | 原国伟,梅俊杰,刘蕻,王以松. 动态速度和代价约束的最短路径算法[J]. 贵州大学学报(自然科学版), 2015, 0(3) |
| |
| 作者姓名： | 原国伟 梅俊杰 刘蕻 王以松 |
| |
| 作者单位： | 贵州大学 计算机科学与技术学院,贵州 贵阳,550025 |
| |
| 基金项目： | 国家自然科学基金不完全知识的遗忘理论研究及应用 |
| |
| 摘 要： | Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法,在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径,即有向图的节点之间除了静态的距离外,还有动态的速度和代价,例如城市交通中的高峰与非高峰时段影响速度/时间,收费与非收费路段影响代价;时间和代价在最短路径中由一个比例因子控制,通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的,实验结果也表明了该算法的有效性。
|
| 关 键 词： | 最短路 动态 代价 Dijkstra算法 |
A Shortest Paths Algorithm with Dynamic SPeeds and Costs Constraint |
| |
| YUAN Guo-wei,MEI Jun-jie,LIU Hong,WANG Yi-song. A Shortest Paths Algorithm with Dynamic SPeeds and Costs Constraint[J]. Journal of Guizhou University(Natural Science), 2015, 0(3) |
| |
| Authors: | YUAN Guo-wei MEI Jun-jie LIU Hong WANG Yi-song |
| |
| Abstract: | |
| |
| Keywords: | shortest paths dynamic cost Dijkstra algorithm |
| 本文献已被 CNKI 等数据库收录！ |
|
