A Faster Shortest Path Algorithm

We present a simple implementation of Dijkstra's shortest path algorithm which (under reasonable assumptions on the data) runs in O (m+n log n) time for networks with n nodes and m arcs. Further improvements are obtained using a modification of the Fibonacci heap data structure as a subroutine.