3. [Negative Dijkstra's Algorithm.] It turns out Dijkstra's algorithm only works for graphs with nonnegative edge weight

[answerhappygod]

3 Negative Dijkstra S Algorithm It Turns Out Dijkstra S Algorithm Only Works For Graphs With Nonnegative Edge Weight 1 (28.26 KiB) Viewed 140 times

3. [Negative Dijkstra's Algorithm.] It turns out Dijkstra's algorithm only works for graphs with nonnegative edge weights. In this question, we'll explore why this is the case. For this question assume that the graph is directed and that all edge weights are integers (a) A "negative cycle" is a cycle where the sum of the edge weights is negative. Why can't we compute shortest paths in a graph with negative cycles? [We are expecting: An informal explanation.] (b) Even if a graph contains no negative cycles (but still contains negative edges) we might still be in trouble. Please draw a graph G, which contains both positive and negative edges but does not contain negative cycles, and specify some source SE V where Dijkstra(G, s) does not correctly compute the shortest paths from S. We are expecting: A graph G and a brief explanation on the shortest path that is not correctly computed.] (c) Consider the algorithm Negative-Dijkstra for computing shortest paths through graphs with negative edge weights (but without negative cycles). This algorithm adds some number to all of the edge weights to make them all nonnegative, then runs Dijkstra on the resulting graph, and argues that the shortest paths in the new graph are the same as the shortest paths in the old graph. Negative-Dijkstra, s): W* = minimum edge weight in G for v in v do for w in v.neighbors do w(e) = w(e) G' = G with weights w' T = Dijkstra(G', s) // run Dijkstra with w' to get a SSSP Tree update I to use weights w that corresponds to graph G return T (Note that an "SSSP tree", or a single-source-shortest-path tree", is analogous to a breadth-first-search tree in that paths in the SSSP tree correspond to shortest paths in the graph. Here we assume that Dijkstra's algorithm has been modified to output such a tree.) Prove or disprove: Negative-Dijkstra always computes single-source shortest paths correctly in graphs with negative edge weights. [We are expecting: To prove the algorithm correct, show that for all u EV. W*

a shortest path from s tou in the original graph lies in T. To disprove the algorithm, exhibit a graph with negative edges, but no negative cycles, where Negative Dijkstra outputs the wrong "shortest" paths, and explain why the algo- rithm fails.