ALCOMFT-TR-01-98

Ulrich Meyer
Directed Single-Source Shortest-Paths in Linear Average-Case Time
MPI. Work packages 2 and 4. May 2001.

Abstract: The quest for a linear-time single-source shortest-path (SSSP) algorithm on directed graphs with positive edge weights is an ongoing hot research topic. While Thorup recently found an O(n+m) time RAM algorithm for undirected graphs with n nodes, m edges and integer edge weights in {0,..., 2^w-1} where w denotes the word length, the currently best time bound for directed sparse graphs on a RAM is O(n+m · loglog n).

In the present paper we study the average-case complexity of SSSP. We give simple label-setting and label-correcting algorithms for arbitrary directed graphs with random real edge weights uniformly distributed in [0,1] and show that they need linear time O(n+m) with high probability. A variant of the label-correcting approach also supports parallelization.

Furthermore, we propose a general method to construct graphs with random edge weights which incur large non-linear expected running times on many traditional shortest-path algorithms.

Postscript file: ALCOMFT-TR-01-98.ps.gz (155 kb).