[CoA 2013] Uri ZWICK - A Forward Backward Single Source Shortest Paths Algorithm in O(n) Time

Deuxièmes journées du GT CoA Complexité et Algorithmes
19-20 novembre, Université Paris Diderot (LIAFA)
--
Exposé invité n°2 : Uri ZWICK (U. Tel-Aviv)
A forward-backward algorithm for single-source shortest paths
--
We present a new algorithm for solving the single source shortest paths problem. The expected running time of the algorithm when run on a complete directed graph with independent exponential edge weights, with sorted incoming and outgoing adjacency lists, is O(n). The novelty of the algorithm is that it uses both incoming and outgoing adjacency lists. Any algorithm that only uses the outgoing adjacency lists requires Ω(n log n) expected time to solve the problem.

Joint work with David Wilson