Shortest paths algorithms: Theory and experimental evaluation

The authors conduct an extensive computational study of shortest paths algorithms, including some very recent algorithms. They also suggest new algorithms motivated by the experimental results and prove interesting theoretical results sugggested by the experimental data. The present computational study is based on several natural problem classes which identify strengths and weaknesses of various algorithms. These problem classes and algorithm implementations form an environment for testing the performance of shortest paths algorithms. The interaction between the experimental evaluation of algorithm behavior and the theoretical analysis of algorithm performance plays an important role in the present research.