3. (5 marks) Consider a directed, edge-weighted graph G with n vertices and its corresponding adja- cency matrix M , whe
Posted: Tue Jul 12, 2022 8:10 am
3. (5 marks) Consider a directed, edge-weighted graph G with nvertices and its corresponding adja-cency matrix M , whereM (i, j) =0, if i = jw((i, j)), if (i, j) is an edge in G+∞, otherwise
Let M 2(i, j) be defined asM 2(i, j) = min{M (i, 1) + M (1, j), M (i, 2) + M (2, j), ..., M(i, n) + M (n, j)}where + is regular addition. What does the value of M 2(i, j) tellus about vertices i and j?Also, what does the value of M k(i, j) tell us about vertices i andj, for any 1 ≤ k ≤ n, whereM k(i, j) = min{M k−1(i, 1) + M (1, j), M k−1(i, 2) + M (2, j),..., M k−1(i, n) + M (n, j)}
Let M 2(i, j) be defined asM 2(i, j) = min{M (i, 1) + M (1, j), M (i, 2) + M (2, j), ..., M(i, n) + M (n, j)}where + is regular addition. What does the value of M 2(i, j) tellus about vertices i and j?Also, what does the value of M k(i, j) tell us about vertices i andj, for any 1 ≤ k ≤ n, whereM k(i, j) = min{M k−1(i, 1) + M (1, j), M k−1(i, 2) + M (2, j),..., M k−1(i, n) + M (n, j)}