A Low-Complexity Binary-Heap Implementation of Dijkstra's Algorithm
Costas K. Constantinou, Georgios Ellinas, Christos G. Panayiotou · arXiv (Cornell University) · 2014
In this paper a new implementation of Dijkstra's algorithm is presented, for the general case of arbitrary directed graphs with unbounded non-negative weights. The proposed implementation utilizes binary heaps and, for a graph consisting of n nodes and m arcs, its computational complexity is of order O(m+n log n).