# Item

ITEM ACTIONSEXPORT

Released

Report

#### Directed single-source shortest-paths in linear average-case time

##### Locator

There are no locators available

##### Fulltext (public)

2001-1-002

(Any fulltext), 11KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Meyer, U.(2001). *Directed single-source shortest-paths in linear
average-case time* (MPI-I-2001-1-002). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-6D44-5

##### 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 ${\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.