Two fast algorithms for all-pairs shortest paths

DOI10.1016/J.COR.2005.10.013MaRDI QIDQ875428zbMATHOpenAlexFDO

Authors Cees Duin

Publication date 13 April 2007

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2005.10.013

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• A branch-checking algorithm for all-pairs shortest paths
• Shortest path methods: A unifying approach
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• scientific article; zbMATH DE number 219247
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$

Cites work

• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• scientific article; zbMATH DE number 3302127 (Why is no real title available?)
• A branch-checking algorithm for all-pairs shortest paths
• A new approach to all-pairs shortest paths on real-weighted graphs
• A note on two problems in connexion with graphs
• All shortest distances in a graph. An improvement to Dantzig's inductive algorithm
• All-pairs shortest paths and the essential subgraph
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Fibonacci heaps and their uses in improved network optimization algorithms
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• Network flows. Theory, algorithms, and applications.
• On a routing problem
• Planar graph decomposition and all pairs shortest paths
• Reduction tests for the steiner problem in grapsh
• Shortest paths algorithms: Theory and experimental evaluation
• Undirected single-source shortest paths with positive integer weights in linear time

Cited in

(19)

• scientific article; zbMATH DE number 1617277 (Why is no real title available?)
• scientific article; zbMATH DE number 1043917 (Why is no real title available?)
• R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks
• A two-criterion lexicographic algorithm for finding all shortest paths in networks
• All pairs lightest shortest paths
• All-pairs shortest paths and the essential subgraph
• A branch-checking algorithm for all-pairs shortest paths
• A blocked all-pairs shortest-paths algorithm
• Shortest path and closure algorithms for banded matrices
• Solving the nearly symmetric all-pairs shortest-path problem
• Solving all-pairs shortest path by single-source computations: theory and practice
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• scientific article; zbMATH DE number 3999136 (Why is no real title available?)
• An algebraic decomposed algorithm for all pairs shortest paths
• Shortest-Path Reconstruction Algorithms
• scientific article; zbMATH DE number 5289563 (Why is no real title available?)
• A priority queue for the all pairs shortest path problem
• A reduction approach to the repeated assignment problem
• All-pairs shortest paths algorithm for high-dimensional sparse graphs

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Two fast algorithms for all-pairs shortest paths

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