Row i, column j: the shortest known distance from i to j, starting from the edges alone (∞ where there is no edge, 0 on the diagonal). Each round admits one more vertex k as a stopover and asks every pair whether going through k is shorter.
Distance matrix for 4 vertices from 7 edges.
Round k = 0: paths may now pass through 0. Row 0 holds the distances out of 0 and column 0 the distances into it, so a candidate for (i, j) is dist[i][0] + dist[0][j].
Round 0. Row and column 0 are the stopover distances.
(1, 1): via 0 costs dist[1][0] + dist[0][1] = 8 + 3 = 11, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
1 to 1 keeps 0.
(1, 3): via 0 costs dist[1][0] + dist[0][3] = 8 + 7 = 15, against ∞ so far. Shorter, so dist[1][3] becomes 15.
1 to 3 improves to 15 via 0.
(2, 1): via 0 costs dist[2][0] + dist[0][1] = 5 + 3 = 8, against ∞ so far. Shorter, so dist[2][1] becomes 8.
2 to 1 improves to 8 via 0.
(3, 1): via 0 costs dist[3][0] + dist[0][1] = 2 + 3 = 5, against ∞ so far. Shorter, so dist[3][1] becomes 5.
3 to 1 improves to 5 via 0.
Round k = 1: paths may now pass through 1. Row 1 holds the distances out of 1 and column 1 the distances into it, so a candidate for (i, j) is dist[i][1] + dist[1][j].
Round 1. Row and column 1 are the stopover distances.
(0, 0): via 1 costs dist[0][1] + dist[1][0] = 3 + 8 = 11, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(0, 2): via 1 costs dist[0][1] + dist[1][2] = 3 + 2 = 5, against ∞ so far. Shorter, so dist[0][2] becomes 5.
0 to 2 improves to 5 via 1.
(3, 2): via 1 costs dist[3][1] + dist[1][2] = 5 + 2 = 7, against ∞ so far. Shorter, so dist[3][2] becomes 7.
3 to 2 improves to 7 via 1.
Round k = 2: paths may now pass through 2. Row 2 holds the distances out of 2 and column 2 the distances into it, so a candidate for (i, j) is dist[i][2] + dist[2][j].
Round 2. Row and column 2 are the stopover distances.
(0, 0): via 2 costs dist[0][2] + dist[2][0] = 5 + 5 = 10, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(0, 3): via 2 costs dist[0][2] + dist[2][3] = 5 + 1 = 6, against 7 so far. Shorter, so dist[0][3] becomes 6.
0 to 3 improves to 6 via 2.
(1, 0): via 2 costs dist[1][2] + dist[2][0] = 2 + 5 = 7, against 8 so far. Shorter, so dist[1][0] becomes 7.
1 to 0 improves to 7 via 2.
(1, 3): via 2 costs dist[1][2] + dist[2][3] = 2 + 1 = 3, against 15 so far. Shorter, so dist[1][3] becomes 3.
1 to 3 improves to 3 via 2.
Round k = 3: paths may now pass through 3. Row 3 holds the distances out of 3 and column 3 the distances into it, so a candidate for (i, j) is dist[i][3] + dist[3][j].
Round 3. Row and column 3 are the stopover distances.
(0, 0): via 3 costs dist[0][3] + dist[3][0] = 6 + 2 = 8, against 0 so far. Not shorter, so the entry stays. Every other pair this round is the same check.
0 to 0 keeps 0.
(1, 0): via 3 costs dist[1][3] + dist[3][0] = 3 + 2 = 5, against 7 so far. Shorter, so dist[1][0] becomes 5.
1 to 0 improves to 5 via 3.
(2, 0): via 3 costs dist[2][3] + dist[3][0] = 1 + 2 = 3, against 5 so far. Shorter, so dist[2][0] becomes 3.
2 to 0 improves to 3 via 3.
(2, 1): via 3 costs dist[2][3] + dist[3][1] = 1 + 5 = 6, against 8 so far. Shorter, so dist[2][1] becomes 6.
2 to 1 improves to 6 via 3.
Every entry is now the shortest distance, 11 updates in all. Three nested loops over 4 vertices: O(n cubed), and negative edges are fine as long as there is no negative cycle.
All pairs done with 11 updates.