A novel pseudo-polynomial approach for shortest path problems

Abstract

This article presents a novel shortest path algorithm for connected networks with nonnegative edge weights. The worst case running time of the single source shortest path version of the algorithm is O( max(m,(vs))) where m is the number of edges of the input network and (vs) is the normalized eccentricity of the source vertex v s. The pseudo-polynomial nature of the time complexity is overcome with a 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.