Suppose that we are given a weighted, directed graph G=(V,E), in which edges that leave the source vertex s may have negative weights, all other edge weights are nonnegative, and there are no negative-weight cycles. We also assume that the graph has no self-loop. In this question we will argue that Dijkstra's algorithm correctly finds shortest paths from s in this graph (Hint: remember the argument using positive weights in the proof of the Dijkstra's algorithm). To do that you will solve the following questions: a. Regarding the proof of the Dijkstra's algorithm for computing the single source shortest path. Indicate which part of this proof relies on the assumption that the graph does not have negative weight cycles. b. Explain why the original proof still holds true in the particular case described above.
Suppose that we are given a weighted, directed graph G=(V,E), in which edges that leave the source vertex s may have negative weights, all other edge weights are nonnegative, and there are no negative-weight cycles. We also assume that the graph has no self-loop.
In this question we will argue that Dijkstra's algorithm correctly finds shortest paths from s in this graph (Hint: remember the argument using positive weights in the proof of the Dijkstra's algorithm). To do that you will solve the following questions:
a. Regarding the proof of the Dijkstra's algorithm for computing the single source shortest path. Indicate which part of this proof relies on the assumption that the graph does not have negative weight cycles.
b. Explain why the original proof still holds true in the particular case described above.
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
