Faster all-pairs shortest paths via circuit complexity
Ryan Williams · 2014
We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two n × n matrices, yielding a faster algorithm for solving the all-pairs shortest path problem (APSP) in dense n-node directed graphs with arbitrary edge weights. On the real RAM, where additions and comparisons of reals are unit cost (but all other operations have typical logarithmic cost), the algorithm runs in time