Design and analysis of sequential and parallel single-source shortest-paths algorithms

Abstract

We study the performance of algorithms for the Single-Source Shortest-Paths (SSSP) problem on graphs with n nodes and m edges with nonnegative random weights. All previously known SSSP algorithms for directed graphs required superlinear time. Wie give the first SSSP algorithms that provably achieve linear O(n-m)average-case execution time on arbitrary directed graphs with random edge weights. For independent edge weights, the linear-time bound holds with high probability, too. Additionally, our result implies improved average-case bounds for the All-Pairs Shortest-Paths (APSP) problem on sparse graphs, and it yields the first theoretical average-case analysis for the "Approximate Bucket Implementation" of Dijkstra's SSSP algorithm (ABI-Dijkstra). Futhermore, we give constructive proofs for the existence of graph classes with random edge weights on which ABI-Dijkstra and several other well-known SSSP algorithms require superlinear average-case time. Besides the classical sequential (single processor) model of computation we also consider parallel computing: we give the currently fastest average-case linear-work parallel SSSP algorithms for large graph classes with random edge weights, e.g., sparse rondom graphs and graphs modeling the WWW, telephone calls or social networks.

In dieser Arbeit untersuchen wir die Laufzeiten von Algorithmen für das Kürzeste-Wege Problem (Single-Source Shortest-Paths, SSSP) auf Graphen mit n Knoten, M Kanten und nichtnegativen zufälligen Kantengewichten. Alle bisherigen SSSP Algorithmen benötigen auf gerichteten Graphen superlineare Zeit. Wir stellen den ersten SSSP Algorithmus vor, der auf beliebigen gerichteten Graphen mit zufälligen Kantengewichten eine beweisbar lineare average-case-Komplexität O(n+m)aufweist. Sind die Kantengewichte unabhängig, so wird die lineare Zeitschranke auch mit hoher Wahrscheinlichkeit eingehalten. Außerdem impliziert unser Ergebnis verbesserte average-case-Schranken für das All-Pairs Shortest-Paths (APSP) Problem auf dünnen Graphen und liefert die erste theoretische average-case-Analyse für die "Approximate Bucket Implementierung" von Dijkstras SSSP Algorithmus (ABI-Dijkstra). Weiterhin führen wir konstruktive Existenzbeweise für Graphklassen mit zufälligen Kantengewichten, auf denen ABI-Dijkstra und mehrere andere bekannte SSSP Algorithmen durchschnittlich superlineare Zeit benötigen. Neben dem klassischen seriellen (Ein-Prozessor) Berechnungsmodell betrachten wir auch Parallelverarbeitung; für umfangreiche Graphklassen mit zufälligen Kantengewichten wie z.B. dünne Zufallsgraphen oder Modelle für das WWW, Telefonanrufe oder soziale Netzwerke stellen wir die derzeit schnellsten parallelen SSSP Algorithmen mit durchschnittlich linearer Arbeit vor.