Shortest path in absence of the given edge

Question

Suppose we are given a weighted graph G(V,E).

The graph contains N vertices (Numbered from 0 to N-1) and M Bidirectional edges .

Each edge(vi,vj) has postive distance d (ie the distance between the two vertex vivj is d)

There is atmost one edge between any two vertex and also there is no self loop (ie.no edge connect a vertex to itself.)

Also we are given S the source vertex and D the destination vertex.

let Q be the number of queries,each queries contains one edge e(x,y).

For each query,We have to find the shortest path from the source S to Destination D, assuming that edge (x,y) is absent in original graph. If no any path exists from S to D ,then we have to print No.

Constraints are high 0<=(N,Q,M)<=25000

How to solve this problem efficiently?

Till now what i did is implemented the simple Dijakstra algorithm.

For each Query Q ,everytime i am assigning (x,y) to Infinity and finding Dijakstra shortest path.

But this approach will be very slow as overall complexity will be Q(time complexity of Dijastra Shortes path)*

Example::

N=6,M=9
S=0 ,D=5

(u,v,cost(u,v))
0 2 4
3 5 8
3 4 1
2 3 1
0 1 1
4 5 1
2 4 5
1 2 1
1 3 3

Total Queries =6

Query edge=(0,1) Answer=7
Query edge=(0,2) Answer=5
Query edge=(1,3) Answer=5
Query edge=(2,3) Answer=6
Query edge=(4,5) Answer=11
Query edge=(3,4) Answer=8

Answer 1

First, compute the shortest path tree from source node to destination.

Second, loop over all the queries and cut the shortest path at the edge specified by the query; this defines a min-cut problem, where you have the distance between the source node and the frontier of one partition and the frontier of the another and the destination; you can compute this problem very easily, at most O(|E|).

Thus, this algorithm requires O(Q|E| + |V|log|V|), asymptotically faster than the naïve solution when |V|log|V| > |E|.

This solution reuses Dijkstra's computation, but still processes each query individually, so perhaps there are room to improvements by exploiting the work did in a previous query in successive queries by observing the shape of the cut induced by the edge.