Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00410
On the ShoshanZwick Algorithm for the AllPairs Shortest Path Problem
Vol. 21, no. 2, pp. 177181, 2017. Concise paper.
Abstract The ShoshanZwick algorithm solves the
allpairs 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^{\omega})$ time,
where $n$ is the number of vertices, $M$ is the largest integer edge cost,
and $\omega < 2.3727$ is the exponent of matrix multiplication.
It is the fastest known algorithm for this problem.
This paper points out and corrects an error in the ShoshanZwick algorithm.

Submitted: August 2016.
Reviewed: November 2016.
Revised: December 2016.
Accepted: December 2016.
Final: December 2016.
Published: January 2017.
Communicated by
Joseph S. B. Mitchell

Journal Supporters
