A forward-backward single-source shortest paths algorithm

DOI10.1137/140970975zbMATH Open1327.68138DBLPjournals/siamcomp/WilsonZ15arXiv1405.7619OpenAlexW2570528627WikidataQ60299126 ScholiaQ60299126MaRDI QIDQ5255013FDOQ5255013

Authors: Uri Zwick, David B. Wilson 

Publication date: 11 June 2015

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

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.

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

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

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)

Cites Work

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

Cited In (5)

• Computing single source shortest paths using single-objective fitness
• Title not available (Why is that?)
• 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)