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. This note points out that the same result can be obtained through simple combinations of standard data structures and with a trivial probabilistic analysis.