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