Recalculating shortest path after changing the weights

I have a weighted, directed graph. I do the following. Given nodes $s$ and $t$ I compute shortest path. Then, I decrease weights of some edges and want to see if there is now another shortest path. Of course, I can recompute shortest path, but I want something faster.

For example, one approach would be to store shortest paths from $s$ to $t$ for every edge in the graph. Then, when I change the weights it takes constant time to check if the shortest path changed (even though, the first step takes much more time). The drawback is that I have to store many paths and to calculate all simple paths in advance, so I'm seeking for alternatives.

So my question is if it's possible to check if the shortest path changed after we decrease edge weights?

Edit: Apparently, this is a problem of dynamic graphs. I didn't delve into the algorithms, so, which algorithm can I use for this problem? I want to improve on running time Dijkstra algorithm.

• You might find this question interesting too. – Juho Oct 27 '15 at 7:01

The standard term for this kind of problem is "dynamic shortest paths" or "shortest paths in a dynamic graph". Here "dynamic" refers to the fact that the graph might be updated, and you want to update the shortest-paths information (hopefully more efficiently than re-computing it from scratch). There are many kinds of updates to the graph one can consider: deleting a vertex, inserting a vertex, deleting an edge, inserting an edge, increasing the length of an edge, decreasing the length of an edge. Your problem is the special case where we only have to deal with decreases to edge weights.

So, I suggest you search the research literature (e.g., using Google Scholar). You should find a bunch of papers that discuss algorithms for this situation.

• I actually did the search already and found similar questions. For example, cs.stackexchange.com/questions/7250/…. The common suggestion is to use D* algorithm. That's okay as an answer, I will look more into this domain. But as far as I know these algorithms are more general than what I'm asking, because they allow for more updates (edge/node deletions, etc.). They also deal with discrete times when to stop searching, while I have O-notation on time. Are there any suggestions how this particular problem can be solved more efficiently. – novadiva Oct 26 '15 at 18:09

For given graph $G$ calculate $d1[v]$ for all vertices $v$ of $G$ where
$d1[v]=length\ of\ shortest\ path\ from \ s \ to \ v \ in\ G$.
For graph $G'$ which is graph $G$ with all its edges reversed calculate $d2[v]$ where
$d2[v]=length\ of\ shortest\ path\ from \ t \ to \ v\ in\ G'$

Let $spl$ be the length of shortest path from s to t in $G$.
For a weight change of edge $uv$ check if $d1[u] + new\_wt(uv) + d2[v] \le spl$.

If previously $uv$ was in some shortest path then $d1[u] + new\_wt(uv) + d2[v]$ will be less than $spl$. Else if it was not on shortest path and $d1[u] + new\_wt(uv) + d2[v] \le spl$ then it will be in shortest path.

(How to check if it was not on shortest path : $d1[u] + old\_wt(uv) + d2[v] > spl$.)

• That's okay, but I change several edges' weights. And then the shortest path can go across only some combinations of the changed edges. This is exponential to the number of changed edges. – novadiva Oct 27 '15 at 7:26