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

Pavlos Eirinakis, Matthew Williamson, K. Subramani

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…