Homework #10:

Problem #1:

Apply D-matrix algorithm described in the first handout (available under Cancas | File as ShortestPath_D_Matrix_algorithm.pdf ) 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⁽¹⁾,

Problem #2:

Apply the F matrix algorithm in the second handout (available under Cancas | File as ShortestPath_F_Matrix_algorithm.pdf ) 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⁽⁰⁾,

(ii) F ⁽¹⁾,

(iii) F ⁽²⁾ ,

(iv) F ⁽³⁾ ,

(v) F ⁽⁴⁾ ,

(vi) F ⁽⁵⁾ ,

(vii) F ⁽⁶⁾.