.png){kind=icon}
Return
An improved Dijkstra's shortest path algorithm for sparse network
.png){kind=icon}
PRE
AI
DOI：10.1016/j.amc.2006.06.094.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
On a network with nonnegative-length edges, Dijkstra's shortest path algorithm computes single-source shortest path in O(m + n log n) time. The time bound assumes that a Fibonacci heap is used during the implementation of Dijkstra's algorithm. As the process of building heaps needs a little complex work, it makes the algorithm not easy to be used. In this paper, we make some very simple, but useful, changes in the original Dijkstra algorithm and obtain a new improved Dijkstra's shortest path algorithm that avoids the process of building heap and runs in O(m + D(max)log(n!)) time. Here m, n and D-max are the number of edges, vertices and the maximal number of edges incident with vertex, respectively. Thus, the new algorithm is very competitive for those sparse networks especially in road traffic networks in which D-max is often a small number. (c) 2006 Elsevier Inc. All rights reserved.
Keywords:
Dijkstra's shortest path algorithm
comparison-addition model
Fibonacci heap
Journal
IF:
3.4
Papers:
2.3W
Citations:
3.3W
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSave
ShareSaveShareSave
ShareSaveShareSaveShareSaveShareSaveShareSave no more
no more