We saw that the Dijkstra shortest-path algorithm may not work if the graph has n

Question

We saw that the Dijkstra shortest-path algorithm may not work if the graph has negative-weight edges. Mr. X proposes to solve this problem as follows. In the given graph, find an edge of minimum negative weight and let it be w, where w > 0. Add w to the weights of all edges to make all edge-weights non-negative. Run the Dijkstra shortest-path algorithm to find the tree of shortest paths. Then subtract w from all edge-weights in the tree.

Does this strategy work? Either prove that it works for all graphs with negative-weight edges, or else give an counterexample showing that it does not work.

Explanation / Answer

Hii there check out the explanation here:

Considering a weighted, directed acyclic graph G = (V, E, w) in which edges that leave the source vertex s may have negative weights and all other edge weights are non-negative.Dijkstra’s algorithm correctly compute the shortest-path weight (s, t) from s to every vertex t in this graph.

For the correctness of Dijkstra, it is sufficient to show that d[v] = (s, v) for every v V when v is added to s. Given the shortest s v path and given that vertex u precedes v on that path, we need to verify that u is in S. If u = s, then certainly u is in S. For all other vertices, we have defined v to be the vertex not in S that is closest to s. Since d[v] = d[u] + w(u, v) and w(u, v) > 0 for all edges except possibly those leaving the source, u must be in S since it is closer to s than v. It was not sufficient to state that this works because there are no negative weight cycles. Negative weight edges in DAGs can break Dijkstra’s in general, so more justification was needed on why in this case Dijkstra’s works.

Also, Given a graph G = (V, E) with positive edge weights, the Bellman-Ford algorithm and Dijkstra’s algorithm can produce different shortest-path trees despite always producing the same shortest-path weights.

Both algorithms are guaranteed to produce the same shortestpath weight, but if there are multiple shortest paths, Dijkstra’s will choose the shortest path according to the greedy strategy, and Bellman-Ford will choose the shortest path depending on the order of relaxations, and the two shortest path trees may be different.

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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