The all-pairs shortest path problem is the determination of the shortest graph distances between every pair of vertices in a
given graph on 
vertices. For nonnegative edge weights, the problem can
be solved using 
applications of Dijkstra's algorithm. The
Floyd-Warshall algorithm also works for
a weighted graph with negative edge weights, provided there is no negative-weight cycle.
The matrix of all distances between pairs of vertices is called the graph distance matrix, or sometimes the all-pairs shortest path matrix.
The graph distance matrix of a graph 
can be found in the Wolfram
Language using GraphDistanceMatrix[g],
and a shortest path between two vertices 
and 
using FindShortestPath[g,
u, v].
Alman and Vassilevska Williams (2026) reported a deterministic algorithm running in 
time on a word random access machine with
-bit
words for a directed graph on 
vertices with polynomially
bounded integer edge weights and no negative-weight cycles.
This refutes the truly subcubic all-pairs shortest path hypothesis. Alman and Vassilevska
Williams (2026) state that Claude discovered the core algorithm,
which they checked and extended, and also report a Lean 4 formalization. The same
method gives a truly subquadratic 3SUM problem algorithm.
