Answer Happy

Urgent pls: Data structures and Algorithms
3. (5 marks) Consider a directed, edge-weighted graph G with n vertices and its corresponding adjacency matrix M, where M(i,j)=⎩⎨⎧​0,w((i,j)),+∞,​ if i=j if (i,j) is an edge in G otherwise ​ Let M2(i,j) be defined as M2(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 M2(i,j) tell us about vertices i and j ? Also, what does the value of Mk(i,j) tell us about vertices i and j, for any 1≤k≤n, where Mk(i,j)=min{Mk−1(i,1)+M(1,j),Mk−1(i,2)+M(2,j),…,Mk−1(i,n)+M(n,j)} Hint: Draw some example directed weighted graphs to figure out what the values represent first.