Computing the diameter polynomially faster than APSP

We present a new randomized algorithm for computing the diameter of a weighted directed graph. The algorithm runs in (M/(+1)n(²+3)/(+1)) time, where < 2.376 is the exponent of fast matrix multiplication, n is the number of vertices of the graph, and the edge weights are integers in \-M,...,0,...,M\. For bounded integer weights the running time is O(n2.561) and if =2+o(1) it is (n7/3). This is the first algorithm that computes the diameter of an integer weighted directed graph polynomially faster than any known All-Pairs Shortest Paths (APSP) algorithm. For bounded integer weights, the fastest algorithm for APSP runs in O(n2.575) time for the present value of and runs in (n2.5) time if =2+o(1). For directed graphs with { positive} integer weights in \1,...,M\ we obtain a deterministic algorithm that computes the diameter in (Mn⁾ time. This extends a simple (n⁾ algorithm for computing the diameter of an { unweighted} directed graph to the positive integer weighted setting and is the first algorithm in this setting whose time complexity matches that of the fastest known Diameter algorithm for { undirected} graphs. The diameter algorithms are consequences of a more general result. We construct algorithms that for any given integer d, report all ordered pairs of vertices having distance { at most} d. The diameter can therefore be computed using binary search for the smallest d for which all pairs are reported.