Directed single-source shortest-paths in linear average-case time
Ulrich Meyer · 2001
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 ${\\cal O}(n+m)$ time RAM algorithm for undirected graphs with $n$ nodes, $m$ edges and integer edge weights in $\\{0,\\ldots, 2^w-1\\}$ where $w$ denotes the word length, the currently best time bound for directed sparse graphs on a RAM is ${\\cal O}(n+m \\cdot \\log\\log 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 $\\left[0,1\\right]$ and show that they need linear time ${\\cal 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.