1. Let G = (V, E) be a directed graph with edge weights w : E R (which may be positive, negative, or zero). Assume there are no negative length cycles in G.

(a) How could we delete an arbitrary vertex v from graph G, without changing the shortest-path distance between any other pair of vertices? Describe and analyze an algorithm that constructs a directed graph G 0 = (V 0 , E 0 ) with edge weights w 0 : E 0 R, where V 0 = V \ {v}, and the shortest-path distance between any two nodes in G 0 is equal to the shortest-path distance between two nodes in G. The algorithm should run in O(V 2 ) time.

(b) Now suppose we have already computed all shortest-path distances in G 0 . Describe and analyze an algorithm to compute the shortest-path distances from v to every other vertex, and from ever other vertex to v, in the original graph G. Again, the algorithm should run in O(V 2 ) time.

(c) Finally, combine parts (a) and (b) to describe and analyze another all-pairs shortest path algorithm. This algorithm should run in O(V 3 ) time. (The resulting algorithm is not the same as Floyd-Warshall!)