A novel pseudo-polynomial approach for shortest paths problems

Abstract

This article presents a novel shortest-paths algorithm for connected networks with non-negative edge weights. The worst case running time of the Single Source Shortest Path version of the algorithm is O(max(m, (epsilon) over cap(nu(s)))) where m is the number of edges of the input network, and (epsilon) over cap(nu(s)), the normalized eccentricity of the source vertex. The pseudo-polynomial nature of the time dependence is overcome with simple speed-up technique. The proposed approach can be implemented on a wide class of shortest-path problems. Approximate solutions can be easily maintained in the preprocessing phase. An experimental efficiency analysis shows that the proposed approach outperforms existing algorithms in total computing time. The proposed algorithm is efficient for all classes of networks and particularly for networks with small diameter.