A forward-backward single-source shortest paths algorithm

DOI10.1137/140970975MaRDI QIDQ5255013zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Uri Zwick, David B. Wilson

Publication date 11 June 2015

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.7619

zbMATH Keywords

shortest pathsrandom graphsaverage case analysis

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Abstract: We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the outgoing and incoming adjacency lists of the vertices appear in non-decreasing order of weight. (Spira's algorithm makes the same assumption about the outgoing adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on $n$ vertices with independent exponential edge weights is $O(n)$, with very high probability. This improves on the previously best result of $O(nlogn)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is $O(n^2)$, matching a recent algorithm of Demetrescu and Italiano as analyzed by Peres et al. Furthermore, the probability that the new algorithm requires more than $O(n^2)$ time is exponentially small, improving on the $O(n^{-1/26})$ probability bound obtained by Peres et al.

Recommendations

• All-pairs shortest paths in \(O(n^2)\) time with high probability
• Single-source shortest-paths on arbitrary directed graphs in linear average-case time
• A bidirectional shortest-path algorithm with good average-case behavior
• Finding real-valued single-source shortest paths in \(o(n^3)\) expected time
• scientific article; zbMATH DE number 986995

Cites work

• scientific article; zbMATH DE number 986995 (Why is no real title available?)
• scientific article; zbMATH DE number 3700238 (Why is no real title available?)
• scientific article; zbMATH DE number 1222607 (Why is no real title available?)
• scientific article; zbMATH DE number 3415384 (Why is no real title available?)
• A New Algorithm for Finding All Shortest Paths in a Graph of Positive Arcs in Average Time $O(n^2 \log ^2 n)$
• A Practical Shortest Path Algorithm with Linear Expected Time
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• A bidirectional shortest-path algorithm with good average-case behavior
• A new approach to all-pairs shortest paths on real-weighted graphs
• A new approach to dynamic all pairs shortest paths
• A note on two problems in connexion with graphs
• A simpler algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
• A simplified algorithm for the all pairs shortest path problem with \(O(n ^{2} \log n)\) expected time
• All-pairs shortest paths in \(O(n^2)\) time with high probability
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Average-case complexity of single-source shortest-paths algorithms: lower and upper bounds
• Buckets, Heaps, Lists, and Monotone Priority Queues
• Correlation inequalities on some partially ordered sets
• Equivalence between priority queues and sorting
• Experimental analysis of dynamic all pairs shortest path algorithms
• Faster algorithms for the shortest path problem
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding the Shortest Route between Two Points in a Network
• On Shortest Paths in Graphs with Random Weights
• On the shortest route through a network
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Probability with Martingales
• Simpler computation of single-source shortest paths in linear average time
• The expected length of a shortest path
• The shortest-path problem for graphs with random arc-lengths
• Time bounds for selection
• Undirected single-source shortest paths with positive integer weights in linear time
• Weak disorder asymptotics in the stochastic mean-field model of distance

Cited in

(5)

• Computing single source shortest paths using single-objective fitness
• scientific article; zbMATH DE number 6850433 (Why is no real title available?)
• A bidirectional shortest-path algorithm with good average-case behavior
• Single backup table schemes for shortest-path routing
• New bounds for old algorithms: on the average-case behavior of classic single-source shortest-paths approaches

This page was built for publication: A forward-backward single-source shortest paths algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5255013)