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

发布时间：2019-01-09 08:59

【摘要】：针对节点约束型最短路径问题,提出了基于回溯法的分层Dijkstra算法,通过分层结构寻找局部最优解来求得全局最优解或次优解.该算法利用分层结构可保存搜索进度的优势,使其在寻找过必经点最短路径时可以实现对搜索进度的保存与回溯等操作.实验结果表明:分层Dijkstra算法虽然增加了一定的空间复杂度,但能有效地减少Dijkstra算法的调用次数;与深度优先搜索、几何代数算法相比,分层Dijkstra算法虽然不一定能找到理论最优解,但出解速度较快,在数据量较大的情况下能快速找到次优解.
[Abstract]:A hierarchical Dijkstra algorithm based on backtracking is proposed to solve the node constrained shortest path problem. The global optimal solution or suboptimal solution is obtained by searching for the local optimal solution through the hierarchical structure. This algorithm utilizes the advantage of hierarchical structure to save the search progress, so that it can save and trace the search progress when searching for the shortest path. The experimental results show that although the hierarchical Dijkstra algorithm increases the space complexity, it can effectively reduce the number of calls to the Dijkstra algorithm. Compared with depth-first search and geometric algebraic algorithm, although the hierarchical Dijkstra algorithm can not always find the theoretical optimal solution, it can quickly find the sub-optimal solution in the case of large amount of data.
【作者单位】： 华南理工大学自动化科学与工程学院;
【基金】：国家自然科学基金资助项目(61573151,61105019) 广东省自然科学基金资助项目(2016A030313468)~~
【分类号】：O157.5

【相似文献】

相关期刊论文 前10条

1 李国成;;Dijkstra算法在物流网络设计中的应用[J];企业导报;2011年18期

2 张美玉;简t$峰;侯向辉;边林洁;梅靖华;;Dijkstra算法在多约束农产品配送最优路径中的研究应用[J];浙江工业大学学报;2012年03期

3 崔小晴;关英子;;存在阻塞路段路网最优路的Dijkstra优化算法[J];旅游纵览(下半月);2013年09期

4 陈荣军;Dijkstra算法的应用[J];常州工业技术学院学报;1999年02期

5 代西武;;Dijkstra矩阵算法[J];北京建筑工程学院学报;2007年02期

6 张福浩;刘纪平;;一种基于Dijkstra的海量空间数据最短路径算法[J];辽宁工程技术大学学报(自然科学版);2009年04期

7 韩伟一,王铮;Dijkstra算法的一个改进[J];运筹与管理;2004年06期

8 刘朝霞;;基于Dijkstra的最短路径问题的算法分析与优化[J];佳木斯教育学院学报;2014年04期

9 熊德国;胡勇文;;用Dijkstra算法求解最短路的矩阵方法[J];河南理工大学学报(自然科学版);2011年05期

10 王华;;基于邻接点算法的Dijkstra优化研究[J];计算机与数字工程;2013年04期

相关会议论文 前1条

1 施培港;;Dijkstra最短路径算法的实现及优化[A];中国地理信息系统协会第三次代表大会暨第七届年会论文集[C];2003年

相关硕士学位论文 前1条

1 刘国华;基于Dijkstra距离的聚类算法研究及其在物流中的应用[D];兰州大学;2011年

，

本文编号：2405408