SHORTEST PATHS ALGORITHMS - THEORY AND EXPERIMENTAL EVALUATION

We conduct an extensive computational study of shortest paths algorith ms, including some very recent algorithms. We also suggest new algorit hms motivated by the experimental results and prove interesting theore tical results suggested by the experimental data. Our computational st udy is based on several natural problem classes which identify strengt hs and weaknesses of various algorithms. These problem classes and alg orithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimenta l evaluation of algorithm behavior and the theoretical analysis of alg orithm performance plays an important role in our research.