A forward-backward algorithm for single-source shortest paths – University of Copenhagen

A forward-backward algorithm for single-source shortest paths

Talk by Uri Zwick

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

Uri Zwick,

Dept. of Computer Science
Tel Aviv Univerusity