On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem

2016/03/29 by Pavlos Eirinakis, Eirinakis, Pavlos, Matthew Williamson +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Exponent #FOS: Computer and information sciences #Graph #Integer (computer science) #Mathematics #Matrix (chemical analysis) #Matrix multiplication #Omega #Optimization and Search Problems #Physics #Shortest path problem #cs.DS

paper · pdf · doi:10.48550/arxiv.1603.08627

published in arXiv (Cornell University) (Cornell University) · 16 pages

arxiv created 2016/03/29 · openalex publication_date 2016/03/29 · arxiv updated 2016/03/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The Shoshan-Zwick algorithm solves the all pairs shortest paths problem in undirected graphs with integer edge costs in the range \1, 2, …, M\. It runs in O(M⋅ n^ω) time, where n is the number of vertices, M is the largest integer edge cost, and ω< 2.3727 is the exponent of matrix multiplication. It is the fastest known algorithm for this problem. This paper points out the erroneous behavior of the Shoshan-Zwick algorithm and revises the algorithm to resolve the issues that cause this behavior. Moreover, it discusses implementation aspects of the Shoshan-Zwick algorithm using currently-existing sub-cubic matrix multiplication algorithms.

Citations

• Algorithm 97: Shortest path
• Fibonacci heaps and their uses in improved network optimization algorithms
• A note on two problems in connexion with graphs

Related

• An expected-case sub-cubic solution to the all-pairs shortest path problem in R
• All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
• Faster Approximate All Pairs Shortest Paths
• Efficient parameterized algorithms for computing all-pairs shortest paths
• Faster all-pairs shortest paths via circuit complexity