Question: Suppose that we are given a weighted, directed graph G=(V,E)in which e

Question

Question: Suppose that we are given a weighted, directed graph G=(V,E)in which edges that leave the source vertix s may havenegative weightes, all other edge weights are nonnegative, andthere are no negative-weight cycles. Argue that Dijkstra'salgrorithm correctly finds the shortest paths from s inthis graph. Dijkstra's Algorith is as follows: DIJKSTRA(G, w, s) { INITIALIZE-SINGLE-SOURCE(G,s) S<-- empty Q<--V[G] while Q empty    do  u<--EXTRACT-MIN(Q)          S<--S U {u}          for eachvertex Adj[u]             doRELAX(u, , w) } I know that this algorithm maintains a set S of verticieswhose final shortest-path weights from the source s havebeen determined from the start, so how are we suppose to provethat Dijkstra's algrorithm correctly finds the shortest pathsfrom s in this graph?

Explanation / Answer

The reason why the Dijkstra’s algorithmcannot handle negative weight edges; is that the total pathweight of previously selected vertex may be longer than to thevertex which is selected in the future. However, if all negativeweight edge is adjacent to source s, then thissituation will never occur. This is because, after the firstiteration, we will not find any negative weight edge and the pathweights will keep on increasing after further relxations.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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