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]

## No comments:

## Post a Comment