Suppose you are given a directed graph G(V, E) with positive weights on the edges, as source vertex s and a destination t. Also, the graph has a special property - the shortest s − t path includes every other vertex in the graph.
Now the edges are vulnerable and can fail. So, you want to maintain alternate shortest path distances between s and t in case some edge e ∈ E fails. Design an O(E log V) algorithm that computes, for all e ∈ E, the shortest s − t path distance in the graph G \ e. Your final output should be an array of size E where the entry for edge e should contain the shortest s − t path distance in G \ e.
