Let G = (V, E) be a connected directed graph with non-negative edge weights, let s and t be vertices of G, and let H be a subgraph of G obtained by deleting some edges. Suppose we want to reinsert exactly one edge from G back into H, so that the shortest path from s to t in the resulting graph is as short as possible. Describe and analyze an algorithm to choose the best edge to reinsert.
I think it need to be used with bellman-ford algorithm for every edge we deleting, and then find the shortest path from all.. but the running time of this is too big.. anyone has anthoer idea? thanks :)
Let e[1] = (u[1],v[1]), e[2] = (u[2],v[2]), ..., e[N] = (u[N], v[N]) be the edges removed from G to get H.
Run Dijkstra's algorithm on H starting from s, keeping track of the cost of the shortest path to each of {u[1], u[2], ..., u[N]}, which we will call A(n) for each node n.
Run Dijkstra's algorithm on H with all edges reversed starting from t, keeping track of the cost of the shortest path to each of {v[1], v[2], ..., v[N]}, which we will call B(n) for each node n.
Then the best single edge to reinsert into H is the edge i such that A(u[i]) + c(e[i]) + B(v[i]) is minimized.
This algorithm runs Dijkstra's algorithm twice, so the complexity of that part is O(|E| + |V|log|V|) where |E| is the number of edges and |V| is the number of nodes.
(I have intentionally ignored the trivial cases of the shortest path from s to t not involving any of the removed edges or no path from s to t existing. They won't cause any problems for the general approach, but you'd need to pay attention to them in an implementation.)