动态速度和代价约束的最短路径算法

• 作者: 刘蕻 原国伟 梅俊杰 王以松
• 来源期刊: 贵州大学学报（自然科学版）
• 学科: 工学
• 关键词: 最短路 动态 代价 Dijkstra算法
• 年，卷（期）: 2015,（3）
• 页码范围: 97-102
• 页数: 6页
• 分类号: TP301
• 字数: 6317字
• 语种: 中文
• DOI: 10.15958/j.cnki.gdxbzrb.2015.03.21

摘要

Dijkstra算法是计算有向图中一个节点到其余各个节点最短路径的著名多项式时间算法，在交通规划、地理信息系统等方面有重要的应用。本文改进Dijkstra算法用于计算带有动态速度和代价约束的有向图中节点之间的最短路径，即有向图的节点之间除了静态的距离外，还有动态的速度和代价，例如城市交通中的高峰与非高峰时段影响速度/时间，收费与非收费路段影响代价；时间和代价在最短路径中由一个比例因子控制，通过调节该比例因子可计算节点间的最短时间/距离和最少代价的路径。该改进的算法被证明是可靠的，实验结果也表明了该算法的有效性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王以松	贵州大学计算机科学与技术学院	23	51	4.0	5.0
2	梅俊杰	贵州大学计算机科学与技术学院	4	6	1.0	2.0
3	刘蕻	贵州大学计算机科学与技术学院	4	6	1.0	2.0
4	原国伟	贵州大学计算机科学与技术学院	3	3	1.0	1.0