Find the shortest paths from node 1 to all other nodes in the graph shown below.

Question

Find the shortest paths from node 1 to all other nodes in the graph shown below. The total weight of the resulting shortest path tree is ______________.

Now, consider all pair shortest paths (shortest paths from each node to all other nodes) for the same graph. ____________ is the only edge that is not used by any shortest path. BTW, write the edge as (x,y).

Now, compute the minimum spanning tree for the graph. ________________ are the edges that are rejected by the MST algorithm. ____________ is the total cost of the MST.

Finally, compute the maximum spanning tree for the graph; it maximizes the total weight instead of minimizing it. ___________ will be the total weight of that maximum spanning tree.

Explanation / Answer

1) he total weight ofthe resulting shortest path tree is 29

2) 1-9 is the only edge that is notused by any shortest path

3)1-7 ,1-8 ,1-9 are the edges that are rejectedby the MST algorithm.

4) 16 is the total cost of theMST.

5) 39 is the total weight of that maximum spanning tree.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects