Meyer, U. (2003). Average-case complexity of single-source shortest-path algorithms: lower and upper bounds. Journal of Algorithms, 48, 91-134.