A forward-backward algorithm for single-source shortest paths

Uri Zwick
Tel-Aviv University

Time: 11am, Aug 12, 2013
Venue: Room 3501

Abstract:

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 Omega(n log n) expected time to solve the problem.

Joint work with David Wilson