Let G (V, E) be a directed graph with weighted edges; edge weights could be positive,...

Transcribed Image Text:

Let G (V, E) be a directed graph with weighted edges; edge weights could be positive, negative or zero. For this problem, let n = |V| a) (10 points) Describe an O(n²) algorithm that takes as input v € V and returns an edge weighted graph G' = (V', E') such that V' = V\{v} and the shortest path distance from u to w in G' for any u, w € V' is equal to the shortest path distance from u to w in G. b) (10 points) Now assume that you have already computed the shortest distance for all pairs of vertices in G'. Give an O(n²) algorithm that computes the shortest distance in G from v to all nodes in V' and from all nodes in V' to v. c) (5 points) Use part (a) and (b) to give a recursive O(n³) algorithm to compute the shortest distance between all pairs of vertices u, v € V. Let G (V, E) be a directed graph with weighted edges; edge weights could be positive, negative or zero. For this problem, let n = |V| a) (10 points) Describe an O(n²) algorithm that takes as input v € V and returns an edge weighted graph G' = (V', E') such that V' = V\{v} and the shortest path distance from u to w in G' for any u, w € V' is equal to the shortest path distance from u to w in G. b) (10 points) Now assume that you have already computed the shortest distance for all pairs of vertices in G'. Give an O(n²) algorithm that computes the shortest distance in G from v to all nodes in V' and from all nodes in V' to v. c) (5 points) Use part (a) and (b) to give a recursive O(n³) algorithm to compute the shortest distance between all pairs of vertices u, v € V.