algorithm for shortest weighted path - frequently changing edges

Question

I'm trying to solve a graph problem. Graph is weighted and undirected.
Graph size:

no. of vertices upto  200,000 
no. of edges upto  200,000 

I've to find a shortest path between given 2 nodes (S & D) in graph. I'm using Dijkstra's algorithm to find this.
Now the problem is graph is frequently changing. I've to find shortest path between S & D, if particular edge is removed from graph. I'm calculating new path again using Dijkstra's algorithm by treating graph as new graph after edge removal. However this approach is too slow as there might be 200,000 edges and I'll be computing shortest path 200,000 times for each edge removal.
I was thinking of using any memoization technique but unable to figure out as shortest path may change altogether if particular edge is removed from graph.
//more details
Source and destination are fixed throughout the problem.
There will be upto 200,000 queries for each edge removal. at a time , only one edge is removed from initial graph for each test case

Answer 1

Since no edge is added, the shortest path after removal will always be greater than than (or equal to) the original. Unless the edge removed is part of the original shortest path, the result will not change. If it is a part of the original shortest path, then running the algorithm again is the worst case solution.

If you are not looking for an exact answer, you could try approximate local methods to fill in the missing edge.

---

You can augment the Dijkstra algorithm to store information which will allow you to backtrack to a particular state during the initial search.

This means that every time you end up changing the shortest path during relaxation, record the changes made to the data-structures, including the heap. That allows you to restore the state of the algorithm to any point during the first run.

When you remove an edge which was on the Shortest Path, you need to go back to the point right before the edge was relaxed, and then restart the algorithm as if the removed edge was never present.