Consider the graph in Figure 25.1 in Cormen 3e p. 690. Now add one edge with weight as follows: w(3, 5) = 3. And, change the weight of edge (1, 3) to -8.

 

A. For this modified graph, identify a negative weight cycle if one exists. (1 point)

B. Now take the above-modified graph and change the -8 to -5, i.e. have w(1, 3) = -5. For this graph, do the following:

Carefully trace Johnson’s algorithm on this modified graph, provided there are no negative weight cycles. If there is one, indicate it; you are done with this problem, and #5 below. (9 points)

For full credit you must complete all four steps:

1. first draw the original graph with the negative weight edges.  

2. Then, show the result of running Bellman-Ford from a super source.

3. Now, show the result after re-weighting edges to remove all negative weight edges.  

4 . Lastly, report the result of running Dijkstra’s algorithm on all pairs (you need not trace out D’s here) in atlas form. Make sure to report distances from the original graph (before the reweighting process).

2 5 2 6 8 4 3