Speeding up shortest path algorithms

DOI10.1007/978-3-642-35261-4_19zbMATH Open1260.68445arXiv1212.6327OpenAlexW1792863046MaRDI QIDQ4909532FDOQ4909532

Authors: Andrej Brodnik, Marko Grgurovič 

Publication date: 21 March 2013

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: Given an arbitrary, non-negatively weighted, directed graph $G=(V,E)$ we present an algorithm that computes all pairs shortest paths in time $mathcalO(m^{\ast }n+mlgn+n{T}_{p}si(m^{\ast },n))$, where $m^{\ast }$ is the number of different edges contained in shortest paths and $T_{p}si(m^{\ast },n)$ is a running time of an algorithm to solve a single-source shortest path problem (SSSP). This is a substantial improvement over a trivial $n$ times application of $psi$ that runs in $mathcalO(n{T}_{p}si(m,n))$. In our algorithm we use $psi$ as a black box and hence any improvement on $psi$ results also in improvement of our algorithm. Furthermore, a combination of our method, Johnson's reweighting technique and topological sorting results in an $mathcalO(m^{\ast }n+mlgn)$ all-pairs shortest path algorithm for arbitrarily-weighted directed acyclic graphs. In addition, we also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP.

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

Recommendations

• Solving all-pairs shortest path by single-source computations: theory and practice
• scientific article; zbMATH DE number 2086613
• Algorithms and Data Structures
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

zbMATH Keywords

all pairs shortest pathsingle source shortest path

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05)

Cited In (11)

• Improved shortest path algorithms for nearly acyclic graphs
• Solving the nearly symmetric all-pairs shortest-path problem
• Fast shortest-paths algorithms in the presence of few destinations of negative-weight arcs
• Title not available (Why is that?)
• Point-to-Point Shortest Path Algorithms with Preprocessing
• Shortest distances as enumeration problem
• Solving all-pairs shortest path by single-source computations: theory and practice
• Title not available (Why is that?)
• Experimental and Efficient Algorithms
• Title not available (Why is that?)
• Computing all-pairs shortest paths by leveraging low treewidth

This page was built for publication: Speeding up shortest path algorithms

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