Meyer, Ulrich Algorithms and Complexity, MPI for Informatics, Max Planck Society;
Meyer, U. (2003). Average-case complexity of single-source shortest-path algorithms: lower and upper bounds. Journal of Algorithms, 48, 91-134.