c. (6 marks) Consider an arbitrary weighted directed graph G = (V, E) with weigh

Question

c. (6 marks) Consider an arbitrary weighted directed graph G = (V, E) with weights er : E ? R {that is, the weights are real numbers). Assume that when you run Dijkstra's shortest path algorithm on G from some vertex s EV to another vertex t e V, you get shortest path Now, consider the same graph G (VE with weights that are double the original weights (i.e. with weights ER such that (e 2(e) for any e e E. Will running Dijkstra's shortest path algorithm on graph G with weights from s to t also produce the same shortest path Xs-r? If so, explain why (in no more than 5 lines). If not, give a counter-example.

Explanation / Answer

yes it will give the same Shortest path. Because it doesn't matter whther you multiply with 2 or 3 or 4 or any number If the edge's weight in graph G say, e1 and e2 has weigth w1 and w2, so if w1 is greater than w2 then you create new edge w1'=2*w1 and w2'=2*w2, w1' will always greate than w2'. In other word, lower weight will remain lower and heigher weight will remain higher in graph, so it will not change path of Shortest path.

PLEASE GIVE THUMBS UP, AND FOR ANY QUERY LEAVE COMMENT. if you face any problem to understan leave comment, we here to help you, Thanks:)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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