Homework #10:

Problem #1:

Apply D-matrix algorithm described in this handout to this directed graph.

(Please use this fixed vertex order v1, v2, v3, v4, v5, v6 on rows and columns when you put down the matrices.)

(i) Write down the matrix D⁽¹⁾ ,

(ii) Calculate and show matrix D⁽²⁾ from D⁽¹⁾ and D⁽¹⁾,

(iii) Calculate and show matrix D⁽³⁾ from D⁽²⁾ and D⁽¹⁾,

(iv) Calculate and show matrix D⁽⁴⁾ from D⁽³⁾ and D⁽¹⁾,

(v) Calculate and show matrix D⁽⁵⁾ from D⁽⁴⁾ and D⁽¹⁾,

(vi) Based on the matrices you got above, what is the minimal path length over all the paths from v2 to v5 using no more than 2 edges, what is the minimal path length over all the paths from v2 to v5 using no more than 3 edges, what is the minimal path length over all the paths from v2 to v5 using no more than 4 edges, what is the minimal path length over all the paths from v2 to v5 using no more than 5 edges, what is the minimal path length over all the paths from v2 to v5 using no more than 6 edges respectively?

(vii) Demonstrate how you can reconstruct a shortest path from v2 to v5 purely based on the matrices D⁽¹⁾ and D⁽⁵⁾ without visual help from the graph above.