Two fast algorithms for all-pairs shortest paths

DOI10.1016/J.COR.2005.10.013zbMATH Open1141.90564OpenAlexW1985732996MaRDI QIDQ875428FDOQ875428

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

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)$

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Cites Work

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

Cited In (14)

• A reduction approach to the repeated assignment problem
• Title not available (Why is that?)
• All pairs lightest shortest paths
• All-pairs shortest paths and the essential subgraph
• Title not available (Why is that?)
• A blocked all-pairs shortest-paths algorithm
• R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks
• A branch-checking algorithm for all-pairs shortest paths
• Shortest-Path Reconstruction Algorithms
• Shortest path and closure algorithms for banded matrices
• Title not available (Why is that?)
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• Title not available (Why is that?)
• A priority queue for the all pairs shortest path problem

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)