Shortest path in absence of the given edge
algorithm, shortest-path
Solution
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.
Problem
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 ```