- Urgent Pls Data Structures And Algorithms 1 (294.12 KiB) Viewed 34 times
Urgent pls: Data structures and Algorithms
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
Urgent pls: Data structures and Algorithms
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.
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.
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!