A new algorithm to find the shortest paths between all pairs of nodes

DOI10.1016/0166-218X(82)90031-2zbMath0471.68043MaRDI QIDQ1157967

Giorgio Gallo, Stefano Pallottino

Publication date: 1982

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

space complexityworst case time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38)

Related Items (3)

All-pairs-shortest-length on strongly chordal graphs ⋮ A new algorithm for reoptimizing shortest paths when the arc costs change ⋮ An auction-based approach for the re-optimization shortest path tree problem

Uses Software

• Algorithm 97
• Algorithm 360

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• A generalized permanent label setting algorithm for the shortest path between specified nodes
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• On a routing problem
• Reoptimization procedures in shortest path problem
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Technical Note—Shortest-Path Algorithms: A Comparison
• Deterministic network optimization: A bibliography
• Shortest-Route Methods: 1. Reaching, Pruning, and Buckets
• Implementation and efficiency of Moore-algorithms for the shortest route problem
• An Appraisal of Some Shortest-Path Algorithms
• Minimum cost routing for static network models
• A Dual Shortest Path Algorithm
• A Theorem on Boolean Matrices

This page was built for publication: A new algorithm to find the shortest paths between all pairs of nodes