已入深夜,您辛苦了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!祝你早点完成任务,早点休息,好梦!

Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue

Dijkstra算法 K最短路径路由 最短路径问题 延氏算法 优先队列 最短路径快速算法 计算机科学 Floyd–Warshall算法 Suurballe算法 算法 约束最短路径优先 图形 排队 数学优化 理论计算机科学 数学 程序设计语言
作者
Sunita Sunita,Deepak Garg
出处
期刊:Journal of King Saud University - Computer and Information Sciences [Elsevier BV]
卷期号:33 (3): 364-373 被引量:46
标识
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.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
烟花的应助被贪玩飞珍采纳,获得10
1秒前
1秒前
青阳子发布了新的文献求助30
3秒前
Jasper的应助被开心的中心采纳,获得10
4秒前
Hello的应助被佚之采纳,获得10
4秒前
曾经的帅哥完成签到,获得积分10
5秒前
12345完成签到 ,获得积分10
6秒前
6秒前
7秒前
7秒前
化学学不明白完成签到,获得积分10
8秒前
911发布了新的文献求助10
8秒前
Michaelfall发布了新的文献求助50
8秒前
丘比特的应助被科研通管家采纳,获得10
8秒前
8秒前
情怀的应助被科研通管家采纳,获得10
8秒前
8秒前
zxy的应助被科研通管家采纳,获得10
9秒前
乐乐的应助被科研通管家采纳,获得10
9秒前
丘比特的应助被科研通管家采纳,获得10
9秒前
华仔的应助被科研通管家采纳,获得10
9秒前
完美世界的应助被科研通管家采纳,获得10
9秒前
9秒前
9秒前
星辰大海的应助被科研通管家采纳,获得10
9秒前
小蘑菇的应助被科研通管家采纳,获得10
9秒前
9秒前
JamesPei的应助被科研通管家采纳,获得10
10秒前
lll完成签到,获得积分10
10秒前
10秒前
嘻嘻哈哈的应助被科研通管家采纳,获得10
10秒前
嘻嘻哈哈的应助被科研通管家采纳,获得10
10秒前
molihuakai的应助被科研通管家采纳,获得10
10秒前
田様的应助被科研通管家采纳,获得10
10秒前
10秒前
无辜汉堡发布了新的文献求助10
10秒前
12秒前
12秒前
12秒前
12秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8184619
求助须知:如何正确求助?哪些是违规求助? 9573576
关于积分的说明 21832380
捐赠科研通 7781845
什么是DOI,文献DOI怎么找? 3434399
关于科研通互助平台的介绍 2558498
邀请新用户注册赠送积分活动 2481003