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

Question

Find the shortest paths from node1 to all other nodes in the graph shown below. The total weight ofthe resulting shortest path tree is .

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

Now, compute the minimum spanningtree for the graph. are the edges that are rejectedby the MST algorithm. is the total cost of theMST.

Finally, compute the maximumspanning tree for the graph; it maximizes the total weight insteadof minimizing it. will be the total weight of thatmaximum spanning tree.

Explanation / Answer

29 . (Using djikstra's algorithm)
(1,9)
(1,7)(1,8)(1,9)
16
39

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.