MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


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

Meyer, Ulrich

May 2001, 32 pages.

Status: available - back from printing

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.

  • Attachement: (409 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Meyer, Ulrich},
  TITLE = {Directed single-source shortest-paths in linear average-case time},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-2001-1-002},
  MONTH = {May},
  YEAR = {2001},
  ISSN = {0946-011X},