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.

Answer 2

My suggestion:

First use Dijkstra to find the shortest path from Source to Destination, but walk from both the source and destination at the same time (use negative distance numbers to indicate how far away from the destination you have traveled), always expand the one with the shortest distance (from either source or destination). Once you encounter a node that has a value from the reverse node then, the path to get to that node is the shortest.

Then remove the edge, if the edge is not part of the shortest path then return the current known shortest path

If the removed edge is part of the shortest path then perform the search again with known absolute distance greater (positive or negative) than the lesser either of the nodes that was removed. Add the previously known shortest path to the known results as positive when walking from the start and negative when walking from the end up to the broken segment. Now search from that starting point in both directions, if you hit a node that has a value set (positive or negative), or was part of the previous shortest path, then you will have found your new shortest path.

The major benefit of doing this is that:

1. you walk from both source and destination so unless your source node is by an edge you wander less nodes overall, and
2. you don't abandon the entire search results, even if the edge removed was the very first edge in the previous shortest path, you just have to find the path to reconnect in the shortest way.

Performance over brute recalculation each time will be considerable, even when the removed node is part of the previously known shortest path.

For how it works, consider this graph:

        I
       /
  B---E
 /   /   H
A   D   /|
 \ / \ / |
  C---F--G

We want to get from A to H, to make it easy lets assume each edge is worth 1 (but it could be anything)

We start at A:

        I
       /
  B---E
 /   /   H
0   D   /|
 \ / \ / |
  C---F--G

Now set the value for H to start at 0:

        I
       /
  B---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  C---F---G

And Expand:

        I
       /
  1---E
 /   /   (0)
0   D   / |
 \ / \ /  |
  1---F---G

Now we expand the next lowest value which will be H:

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

Now we arbitrary pick B because it comes before C, F or G (they have the same absolute value):

        I
       /
  1---2
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1---(-1)--(-1)

Then C

        I
       /
  1---2
 /   /        (0)
0   2        /  |
 \ / \      /   |
  1---2 & (-1)--(-1)

Now we have a node that knows both it's positive value and it's negative value, hence we know it's distance to both A and H and since we were expanding the shortest node first this must be the shortest path, therefore we can say that the shortest path from A to H is A->C->F->H and costs ABS(2)+ABS(-1) = 3

Now suppose we removed the line C->F I / 1---2 / / (0) 0 2 / | \ / \ / | 1 2 & (-1)--(-1)

We then remove all known values with an absolute value above the lesser value of C and F (in this case is 1) leaving:

        I
       /
  1---E
 /   /     (0)
0   D     /  |
 \ / \   /   |
  1   (-1)--(-1)

Now again we expand as before, starting with B: I / 1---2 / / (0) 0 D / | \ / \ / | 1 (-1)--(-1)

Then C

        I
       /
  1---2
 /   /     (0)
0   2     /  |
 \ / \   /   |
  1   (-1)--(-1)

Now F:

        I
       /
  1---2
 /   /         (0)
0   2&(-2)    /  |
 \ /    \    /   |
  1      (-1)---(-1)

Hence we know the shortest path from A to H is now: A->C->D->F->H and costs ABS(2)+ABS(-2) = 4

This will work with any number of nodes, edges and edge weights, in the event that you have no further nodes to expand then you return your "No Route" response.

You can further optimize it by not resetting the node values of nodes that were in the previous shortest path, in doing so you lose the simple nature but it's not overly complex.

In the above example it wouldn't make a difference initially, but it would make a difference if we then removed the linkage A->C because we would remember the costs of C and the other nodes in the chain (as negative)

The benefit over just using a single-sided Dijkstra and rolling back to before the removed edge can be shown below:

        I
       /
  1---E
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

Now we would expand B:

        I
       /
  1---2
 /   /   H
0   D   /|
 \ / \ / |
  1   F--G

C:

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   F--G

D:

        I
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

E:

        3
       /
  1---2
 /   /   H
0   2   /|
 \ / \ / |
  1   3--G

F:

        3
       /
  1---2
 /   /   4
0   2   /|
 \ / \ / |
  1   3--4

And then we would determine the path is now A->C->D->F->H and it costs 4. Notice we needed to do 5 expand steps here, compare that to the 3 that we needed for the by-directional way.

As the removed edge gets more towards the middle of the path we will get a greatly improved saving by using a bi-directional graph walking algorithm to recalculate the new path. Unless there's say 50 nodes hanging off H but only a single path all the way from A to H but that's a fringe case and unlikely to happen in a normal network, in the event that it does this will still work good on average, in contrast to the reverse where there is only one direct path from H to A but 50 edges attached to A.

Given you have some ~200,000 edges with potentially up to 200,000 nodes, you're likely going to see considerable savings compared to my example graph which has only 9 nodes and 11 edges. This is based on the idea that we're looking for the algorithm that has the fewest node expansions as they are likely where the majority of the computational time will be spent looping over.

Answer 3

I have an idea:

• First time do a Dijkstra and memorize all the edge's for the shortest path from Source to Destination.
• When you make a removal you check if you deleted an edge from your shortest path. If no the result is the same. If yes you do another Dijkstra.

Another idea:

• First perform a Dijkstra and for each vertex keep in mind all the elements that depend of that vertex.
• When you perform a removal you should do something like a Topological Sorting and for all the vertex that depends on your vertex do an update and with those vertex perform a partial Dikstra.

Answer 4

If the removed edge is not from the shothest path, than the path will remain the same. Otherwise there is probably no good exact solution, because the problem is monotonic - shorthest path sp from A to B (sp(A, B)) using node C consists of all shorthest paths such that sp(A, B) = sp(A, C) + sp(C, B) (for all C).

By removing one (very good) edge you may destroy all of these paths. The best solution (but not exact) might be to use Floyd-Warshall algorithm to calculate all shorthest path between all pairs of nodes and that, after removal of the edge from path try to repair the path by using the shorthest detour.