algorithm - Shortest path in absence of the given edge -

suppose given weighted graph g(v,e).

the graph contains n vertices (numbered 0 n-1) , m bidirectional edges .

each edge(vi,vj) has postive distance d (ie distance between 2 vertex vivj d)

there atmost 1 edge between 2 vertex , there no self loop (ie.no edge connect vertex itself.)

also given s source vertex , d destination vertex.

let q number of queries,each queries contains 1 edge e(x,y).

for each query,we have find shortest path source s destination d, assuming edge (x,y) absent in original graph. if no path exists s d ,then have print no.

constraints high 0<=(n,q,m)<=25000

how solve problem efficiently?

till now did implemented simple dijakstra algorithm.

for each query q ,everytime assigning (x,y) infinity , finding dijakstra shortest path.

but approach slow overall complexity 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 

first, compute shortest path tree source node destination.

second, loop on queries , cut shortest path @ edge specified query; defines min-cut problem, have distance between source node , frontier of 1 partition , frontier of , destination; can compute problem easily, @ o(|e|).

thus, algorithm requires o(q|e| + |v|log|v|), asymptotically faster naïve solution when |v|log|v| > |e|.

this solution reuses dijkstra's computation, still processes each query individually, perhaps there room improvements exploiting work did in previous query in successive queries observing shape of cut induced edge.