A novel linear algorithm for shortest paths in networks

Abstract

We present two new linear algorithms for the single source shortest paths problem. The worst case running time of the first algorithm is O(m+C log C), where m is the number of edges of the input network and C is the ratio of the largest and the smallest edge weight. The pseudo-polynomial character of the time dependence can be overcome by the fact that Dijkstra's kind of shortest paths algorithms can be implemented "from the middle", when the shortest paths to the source are known in advance for a subset of the network vertices. This allows the processing of a subset of the edges with the proposed algorithm and processing of the rest of the edges with any Dijkstra's kind algorithm afterwards. Partial implementation of the algorithm enabled the construction of a second, highly efficient and simple linear algorithm. The proposed algorithm is efficient for all classes of networks and extremely efficient for networks with small C. The decision which classes of networks are most suitable for the proposed approach can be made based on simple parameters. Experimental efficiency analysis shows that this approach significantly reduces total computing time.