On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs

摘要

We present an algorithm, APD, that solves the distance version of the all-pairs-shortest-path problem for undirected, unweighted n-vertex graphs in time O(M(n) log n), where M(n) denotes the time necessary to multiply two n × n matrices of small integers (which is currently known to be o(n2.376)). We also address the problem of actually finding a shortest path between each pair of vertices and present a randomized algorithm that matches APD in its simplicity and in its expected running time.