Let G (V,E) be a connected directed graph with non-negative edge lengths, let s and t be vertices of G. Suppose you computed the shortest path distances and a shortest path tree T from s using Dijkstra's algorithm. Not to submit: Suppose you only computed the shortest path distances and forgot to compute the tree T. Describe how you can compute a shortest path tree in linear time . . After you did your shortest path computation you wanted to add a new edge e - (u, v) with length l(e) to your graph. Of course you can recompute the shortest path distances (and the tree) using Dijkstra's algorithm in the graph H which is the graph obtained from G by adding (u, v). Describe a linear time algorithm that can do this without running Dijkstra's algorithm again. It may help you to see if the adding the edge would change any distances at all. Now consider the case when you want to delete an edge e - (u, v) from the graph G. Describe a linear time algorithm that computes the new shortest path distances from s in the graph G -e Let G (V,E) be a connected directed graph with non-negative edge lengths, let s and t be vertices of G. Suppose you computed the shortest path distances and a shortest path tree T from s using Dijkstra's algorithm. Not to submit: Suppose you only computed the shortest path distances and forgot to compute the tree T. Describe how you can compute a shortest path tree in linear time . . After you did your shortest path computation you wanted to add a new edge e - (u, v) with length l(e) to your graph. Of course you can recompute the shortest path distances (and the tree) using Dijkstra's algorithm in the graph H which is the graph obtained from G by adding (u, v). Describe a linear time algorithm that can do this without running Dijkstra's algorithm again. It may help you to see if the adding the edge would change any distances at all. Now consider the case when you want to delete an edge e - (u, v) from the graph G. Describe a linear time algorithm that computes the new shortest path distances from s in the graph G -e