Homework #10:

 

Problem #1:

 

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

HW4-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(1) ,

(ii)             Calculate and show matrix D(2) from D(1) and D(1),

(iii)          Calculate and show matrix D(3) from D(2) and D(1),

(iv)           Calculate and show matrix D(4) from D(3) and D(1),

(v)             Calculate and show matrix D(5) from D(4) and D(1),

(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(1) and D(5)  without visual help from the graph above.

 

 

Problem #2:

Apply the F matrix algorithm in the second handout (i.e. the Floyd-Warshall algorithm) to the directed graph above to calculate and show the matrices (with the vertex order v1, v2, v3, v4, v5, v6 on rows and columns)

(i)               F(0),

(ii)             F (1),

(iii)          F (2) , 

(iv)           F (3) ,

(v)             F (4) ,

(vi)           F (5) ,

(vii)        F (6).

(viii)      Based on the matrices F(0) and  F (6) alone  without visual help from the graph above, demonstrate how you can determine the shortest distance from v2 to v5 and how to reconstruct a shortest path from v2 to v5. NOTE that the matrices denoted by the notation F (i) here are different from the matrices D(i) derived by the matrix method used in Problem #1.