Dijkstra算法
K最短路径路由
最短路径问题
延氏算法
优先队列
最短路径快速算法
计算机科学
Floyd–Warshall算法
Suurballe算法
算法
约束最短路径优先
图形
排队
数学优化
理论计算机科学
数学
程序设计语言
作者
Sunita Sunita,Deepak Garg
标识
DOI:10.1016/j.jksuci.2018.03.003
摘要
Dynamic shortest path algorithms are the ones which are used to accommodate the online sequence of update operations to the underlying graph topology and also facilitate the subsequent query operations. Many solutions exist for the different versions of the problem, all of which identify the set of vertices whose shortest paths may be affected by the changes and then update their shortest paths according to the update sequence. In this paper, we are dynamizing the Dijkstra algorithm which helps to efficiently solve the dynamic single source shortest path problem. Dynamization is achieved by using the retroactive priority queue data structure. Retroactive data structure identify the set of affected vertices step by step and thus help to accommodate the changes in least number of computations. So, with a suitable dynamic graph representation and the use of retroactive priority queue, we have proposed algorithm to dynamize Dijkstra algorithm giving solution of dynamic single source shortest path problem with complexity O(nlg m) for the update time. We have performed experimental analysis by comparing the performance of the proposed algorithm with other algorithms. Our experimental results indicate that the proposed algorithm has better performance in terms of time and memory usage.
科研通智能强力驱动
Strongly Powered by AbleSci AI