Negative weight edges. Professor Gecko suggests that we deal with graphs with negative weight edges in the following way:

1.Scan the adjacency list and find the most negative edge weight, call it x.

2.Add |x| + 1 to the weight of each edge. Then, each edge will have positive weight.

3.We run whatever algorithm we want that works for graphs with non-negative edge weights.

4.Subtract |x| + 1 from the weight of each edge to return each edge weight to its original value.

Steps 1, 2 and 4 can be completed in O( V + E ) time, so they can be accomplished efficiently. Do the following:

a. Argue that Professor Gecko's suggestion works for the minimum spanning tree problem

b. Argue that Professor Gecko's suggestion does not work for the signle-source shortest path problem (i.e., when "whatever algorithm" is Dijkstra's algorithm.)