Shortest path (deriving)

A graph G contains n vertices {1, 2, ... n} and is represented by its adjacency matrix, A.
Write code to transform A, such that, A[i, j] is the shortest path from vertex i, to vertex j.

Given that n = 4 and A is
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

derive the matrix of shortest paths, showing the matrix after each of the 4 major steps.

Solution

for k = 1 to n
for i = 1 to n
for j=1 to n
A[i, j] = min(A[i, j], A[i, k] + A[k, j]) [2 marks]

A:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 9 0

k=1:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 ∞
3 ∞ 7 0

k=2:
0 ∞ 4 ∞
∞ 0 ∞ 7
18 5 0 12
3 ∞ 7 0

k=3:
0 ∞ 4 16
∞ 0 ∞ 7
18 5 0 ∞
3 12 9 0

k=4:
0 ∞ 4 16
10 0 14 7
18 5 0 ∞
3 12 9 0

[5 marks]