
An ef?cient algorithm for the shortest path problem
Diab Abuaiadh and Jeffrey H. Kingston
ABSTRACT
A hybrid algorithm for the shortest path problem is presented. Its time
complexity is O(n + m) when the graph is acyclic and O(nlogc? + m) in general,
where c? < n. The main improvement comes from a modi?cation of Fibonacci
heaps, in which the amortized time complexity of n Delete and c? FindMin
operations is O(nlogc?).
23 February, 1993