Single-Source Shortest-Paths on Arbitrary Directed Graphs in Linear Average-Case Time

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 a simple algorithm for arbitrary directed graphs with random edge weights uniformly distributed in $\left[0,1\right]$ and show that it needs linear time ${\cal O}(n+m)$ with high probability