6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ You might find this question interesting too. $\endgroup$
    – Juho
    Oct 27, 2015 at 7:01

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – novadiva
    Oct 26, 2015 at 18:09
  • $\begingroup$ @novadiva, for future reference: we expect you to tell us in the question what research you've already done, and what approaches you've already considered and rejected (and why). If you've already found something but don't tell us about it, then you risk wasting answerers time when they write an answer mentioning that thing you already knew about... At this point I suggest editing your question to list the best algorithm you currently know of, and to ask whether there exists a more efficient algorithm -- be sure to tell also tell us what metric for efficiency you want us to use. $\endgroup$
    – D.W. ♦
    Oct 26, 2015 at 18:11
1
$\begingroup$

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 $.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – novadiva
    Oct 27, 2015 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.