Meyer as well as Goldberg recently described algorithms that solve the single-source shortest-paths problem in linear average time on graphs with random edge lengths drawn from the uniform distribution on [0, 1]. This note points out that the same result can be obtained through simple combinations of standard data structures and with a trivial probabilistic analysis.
['Torben Hagerup']
Simpler computation of single-source shortest paths in linear average time