In all pairs shortest path, the solution is the [[shortest path]] between all pairs of vertices. The output is a matrix of costs for each node pair and a **next matrix** which captures the node that comes next in the shortest path from nodes $i$ to $j$. To find the shortest path, recursively construct the path from the next matrix.