A fast algorithm for finding all shortest paths

DOI10.1016/0020-0190(81)90139-3zbMath0469.68070OpenAlexW2046356740MaRDI QIDQ1157176

Osamu Watanabe

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90139-3

zbMATH Keywords

directed graphmatrix multiplicationall-pairs shortest path problem

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 (1)

Graph theory (algorithmic, algebraic, and metric problems)

Cites Work

• Unnamed Item
• Shortest-path problem is not harder than matrix multiplication
• An algorithm for finding all shortest paths using \(N^{2\cdot 81}\) infinite-precision multiplications
• Gaussian elimination is not optimal

This page was built for publication: A fast algorithm for finding all shortest paths