节点约束型最短路径的分层Dijkstra算法

被引：85

作者：

康文雄

许耀钊

机构：

[1] 华南理工大学自动化科学与工程学院

来源：

华南理工大学学报(自然科学版) | 2017年 / 45卷 / 01期

基金：

广东省自然科学基金;

关键词：

路由算法; 最短路径; 节点约束型; 回溯法; 贪心算法;

D O I：

暂无

中图分类号：

O157.5 [图论];

学科分类号：

070101 [基础数学];

摘要：

针对节点约束型最短路径问题,提出了基于回溯法的分层Dijkstra算法,通过分层结构寻找局部最优解来求得全局最优解或次优解.该算法利用分层结构可保存搜索进度的优势,使其在寻找过必经点最短路径时可以实现对搜索进度的保存与回溯等操作.实验结果表明:分层Dijkstra算法虽然增加了一定的空间复杂度,但能有效地减少Dijkstra算法的调用次数;与深度优先搜索、几何代数算法相比,分层Dijkstra算法虽然不一定能找到理论最优解,但出解速度较快,在数据量较大的情况下能快速找到次优解.

引用

页码：66 / 73

页数：8

共 17 条

[1]

实际路网最短路径算法优化与实现 [D].