# An expected-case sub-cubic solution to the all-pairs shortest path problem in R

Preprint · Julian J. McAuley, Tibério S. Caetano

- Archive id: arxiv:0912.0975
- Published: 2009-12-05
- arXiv: https://arxiv.org/abs/0912.0975
- Source URL: https://arxiv.org/abs/0912.0975
- PDF: https://arxiv.org/pdf/0912.0975
- Provenance: arxiv

## Abstract

It has been shown by Alon et al. that the so-called 'all-pairs shortest-path' problem can be solved in O((MV)^2.688 \* log^3(V)) for graphs with V vertices, with integer distances bounded by M. We solve the more general problem for graphs in R (assuming no negative cycles), with expected-case running time O(V^2.5 \* log(V)). While our result appears to violate the Omega(V^3) requirement of "Funny Matrix Multiplication" (due to Kerr), we find that it has a sub-cubic expected time solution subject to reasonable conditions on the data distribution. The expected time solution arises when certain sub-problems are uncorrelated, though we can do better/worse than the expected-case under positive/negative correlation (respectively). Whether we observe positive/negative correlation depends on the statistics of the graph in question. In practice, our algorithm is significantly faster than Floyd-Warshall, even for dense graphs.

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

---
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.