Simpler Computation of Single-Source Shortest Paths in Linear Average Time

摘要

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.