Algorithms for Shortest Paths

Abstract

New algorithms are presented for the general all pairs and single source shortest path problems and for the single source problem restricted to nonnegative arc weights. The new algorithms are faster on sparse networks than algorithms previously known. In addition, new results are presented on the behavior of well-known algorithms, two of which have exponential running times under surprisingly innocuous conditions.