All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph.
We strengthen the previously formalized bound to for deterministic APSP on directed graphs with polynomially bounded integer weights and no negative cycles, using the same word-RAM model. It formalizes the improvement outlined by Alman and Vassilevska Williams in their conclusion.
theorem APSPExponentImprovement.apsp :
TrulySubcubicAPSP.APSP.SolvedInTime 2.9983 := by sorryCompute all exact shortest-path distances in a directed n-vertex graph with integer weights and no negative-weight closed walk in deterministic word-RAM steps, where exactly. Negative edges and missing edges are permitted. For each ordered vertex pair, output a reachability flag followed by a distance: flag one requires an attained minimum path weight, and flag zero requires that no path exists, with the distance slot then unrestricted. Empty paths give diagonal distance zero. For every fixed natural weight exponent , there must be a single finite deterministic word-RAM program, a word-width constant , and a time bound working for all sizes and all word widths . Every encoded input integer has absolute value at most . Correctness includes ; the asymptotic bound is required for . The machine must accept and write the required exact output. There are no hypotheses assuming the supporting algorithms or any complexity conjecture.
No open leaves. Every sub-goal is proved or awaiting decomposition.