Let G be a directed weighted graph, where V(G) = {v1, v2,..., vn}. Let B be an n * n matrix

such that entry bij denotes the distance in G from vi to vj (using a directed path). Now we

are going to insert a new vertex vn+1 into G. Let wi denote the weight of the edge (vi, vn+1) and w'i denote the weight of the edge (vn+1; vi). (If there is no edge from vi to vn+1 or from vn+1 to vi, then wi or w'i is inf, respectively.) Describe an algorithm to construct an (n + 1) * (n + 1) distance matrix B' from B and values of wi and w'i for 1 =

Let G be a directed weighted graph, where V(G) v1, v2, nt. Let B be an n x n matrix such that entry bij denotes the distance in G from vi to v (using a directed path). Now we are going to insert a new vertex vn+1 into G. Let wi denote the weight of the edge (vi, vm+1) and wi denote the weight of the edge (vm+1, vi). (If there is no edge from vi to vn+1 or from vn+1 to vi, then wi or wi is inf, respectively.) Describe an algorithm to construct an (n 1) x (n 1) distance matrix B" from B and values of wi and w i for 1 S i S n. (Note that the graph G itself is not given.) Your algorithm should work in O(n2) time. (Hint: Use the Floyd's dynamic programming algorithm for finding all pairs shortest paths.) Let G be a directed weighted graph, where V(G) v1, v2, nt. Let B be an n x n matrix such that entry bij denotes the distance in G from vi to v (using a directed path). Now we are going to insert a new vertex vn+1 into G. Let wi denote the weight of the edge (vi, vm+1) and wi denote the weight of the edge (vm+1, vi). (If there is no edge from vi to vn+1 or from vn+1 to vi, then wi or wi is inf, respectively.) Describe an algorithm to construct an (n 1) x (n 1) distance matrix B" from B and values of wi and w i for 1 S i S n. (Note that the graph G itself is not given.) Your algorithm should work in O(n2) time. (Hint: Use the Floyd's dynamic programming algorithm for finding all pairs shortest paths.)