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

Article · Pavlos Eirinakis, Matthew Williamson, K. Subramani

- Archive id: arxiv:1603.08627
- Published: 2016-03-29
- Venue: Journal of Graph Algorithms and Applications
- DOI: https://doi.org/10.7155/jgaa.00410
- arXiv: https://arxiv.org/abs/1603.08627
- Citations: 1
- Source URL: https://arxiv.org/abs/1603.08627
- PDF: https://arxiv.org/pdf/1603.08627
- Provenance: arxiv

## Abstract

The Shoshan-Zwick algorithm solves the all pairs shortest paths problem in undirected graphs with integer edge costs in the range $\\{1, 2, \\dots, M\\}$. It runs in $\\tilde{O}(M\\cdot 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.