Question: i have the answer below, However, is it possible to get illustrations to understand it properly please? (e) DT computes a shortest-path tree in a

 i have the answer below, However, is it possible to get

i have the answer below, However, is it possible to get illustrations to understand it properly please?

illustrations to understand it properly please? (e) DT computes a shortest-path tree

(e) DT computes a shortest-path tree in a given graph G = (V. E) using Dijkstra's algorithm. DT claims that this is the MST of G. Is DT right or wrong? Prove your answer. (f) DT also claims that a shortest path between two nodes of the given graph G = (V, E) is part of some MST of G. Is DT right or wrong? Prove your answer. (e) DT's claim is : Right Proof We know Dijkstra's formula produces set of edges for single source shortest path, So, the output could be a tree containing all vertices of given graph, So, it,s a spanning tree. To prove the computed spanning tree could be a minimum spanning tree assume that there are some edges in MST that isn't in Dijkstra's output Let, vl,v2,v3 be 3 vertices. v1 is in MST however not in Dijkstra's output v3 is reached from v2. (v2->3) in Dijkstra's output Now, as Dijkstra's haven't thought of the edge vi>v3 to achieve v3, therefore the weight ofv1- 3 is more than v2->v3. So, in MST by discarding v1->v3 and adding v2->v3, the entire weight will be further decreased So, our assumption isn't correct, Hence all Dijkstra's edges are in MST (f)DT's claim is : Right Proof assume there exists a shortest path from vi to vj that's not a part of any MST.So, the weight ofpath from vi to vj in MST is either more than shortest path between vi and vj or there exists another path with same weight. For initial case,), MST weight will be decreased by adding edges in shortest path and discarding different edges, therefore computed MST isn't correct ANd shortest path from vi tovj is a component on an MST for second case,(there exists another path with same weight.), the trail in MST is additionally an shortest path from vi to vj. i.e. shortest path from vi to vj part of an MST

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!