<p>your question seems quite advanced and it seems unlikely anyone has considered the incremental problem for the particular algorithm you are implementing when the new nonincremental algorithm was published by Yanagisawa as recently as 2010.</p>

<p>the algorithm you cite is apparently designed to be parallelizable therefore that seems like the 1st approach to optimizing it. ie implement it in a highly parallel implementation and just recompute all paths.</p>

<p>I have not seen a paper describing this, but how about this approach which seems to work in theory &amp; in general but details could be tricky (maybe it appears in a paper somewhere-- would be interested if anyone has seen a similar technique). every algorithm to solve the problem must basically reduce to a (2-way?) comparison of edge weights. the resulting paths are built out of the results of these comparisons. the "comparison tree" for every optimal path can be stored during the 1st computation of all pairs. </p>

<p>then when any weights are changed, traverse through all prior stored/built-up comparison trees to recompute the answer. probably, for small changes, one would not have to descend "deeply" into those trees because the results of some or "many" prior comparisons are unchanged. one may have to modify the trees if new "comparison paths" in the trees are triggered but again this might not be expensive. however there would be a threshold where it is simpler to recompute everything from scratch when there are too many weight changes.</p>

<p>the main question of course is the memory cost of storing all the comparison trees.</p>

<p><sup>
(fineprint: and if all this actually worked, it would likely be a significant advance &amp; publishable result.)
</sup></p>

CC BY-SA 3.0
2012-02-01T21:47:33.050Z
2012-02-01T21:47:33.050Z
vzn
<p>And in what kinds of updates are you interested? Both weight increase and decrease? Obviously, it should not be hard to solve edge increases since such an update influences only those optimal paths containing the changed edge and it is not hard to recomputed them quickly (actually, it can be done even more efficiently). Weight decrease is harder case but it does not make sense in route planning practice (usually). </p>

<p>Anyway, if you are already using some route planning (all pairs shortest path) approach, you should look for its "dynamization". I would not consider heuristics since I am not aware of any good heuristic route planning algorithm. </p>

<p>So what kind of updates are we talking about?</p>

CC BY-SA 3.0
2012-02-01T06:21:10.127Z
Hello,Thanks for the reply.By updates I mean, both the increase & decrease. Basically every road has a score, depending upon the traffic at that edge,the score can decrease and increase. So the algorithm needs to adapt so that it can provide the shortest path considering the updates in all the shortest paths it has already found rather than re-finding all pair shortest paths.Can you please explain/provide link for the update part, I mean how would it be effective for all pairs? Secondly from the second para, apart from all pairs shortest path approach, can there be any other effective approach
Jatin
CC BY-SA 3.0
2012-01-31T23:21:37.263Z
2012-01-31T23:21:37.263Z
Ondrej Moris
<p>I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network.  <a href="https://cstheory.stackexchange.com/questions/9804/all-pair-shortest-path-problem-for-large-number-of-nodes/9814#9814">An answer to my previous question</a> led me to Hiroki Yanagisawa's paper "<a href="http://www.research.ibm.com/trl/people/yanagis/papers/IPDPS2010_yanagisawa.pdf" rel="nofollow noreferrer">A multi-source label-correcting algorithm for the all-pairs shortest paths problem</a>" [IPDPS 2010] which is performing really well.</p>

<p>But what about updates?  I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes.  On researching, I came across a paper "<a href="http://u.cs.biu.ac.il/~liamr/papers/OnDynamicShortestPath.pdf" rel="nofollow noreferrer">On Dynamic Shortest Path problems</a>", which states that </p>

<blockquote>
  <p>Reductions that show that the incremental and decremental single-source
  shortest-paths problems, for weighted directed or undirected
  graphs, are, in a strong sense, at least as hard as the static all-pairs
  shortest-paths problem. </p>
</blockquote>

<p>So the question is: <b>Are there useful heuristic approaches to solve this problem?</b></p>

CC BY-SA 3.0
2012-01-30T17:14:10.153Z
I think that it is unfair to say “On researching through many papers finally concluded with …” without acknowledging the [answer](http://cstheory.stackexchange.com/a/9814/567) you received in your previous question which gave the reference to exactly the same paper.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-30T22:27:13.697Z
The here link is to **this** question instead of the other. :-/
Michel de Ruiter
CC BY-SA 3.0
2012-01-31T02:23:33.547Z
Edited for clarity and grammar; fixed broken link to previous answer.
Jeffε
CC BY-SA 3.0
2012-02-01T13:16:32.397Z
Perhaps this paper can help you: http://db.csail.mit.edu/pubs/cq_icde_cr.pdf
Marzio De Biasi
<graph-theory><graph-algorithms>
Edge-weight updates in all pair shortest path problem
Jatin
# Edge-weight updates in all pair shortest path problem

(Asked by: username_0 on 2012-01-30)

I want to calculate all-pairs shortest paths on a graph with roughly 50,000 nodes representing a city-wide road network. [An answer to my previous question](https://cstheory.stackexchange.com/questions/9804/all-pair-shortest-path-problem-for-large-number-of-nodes/9814#9814) led me to Hiroki Yanagisawa's paper "[A multi-source label-correcting algorithm for the all-pairs shortest paths problem](http://www.research.ibm.com/trl/people/yanagis/papers/IPDPS2010_yanagisawa.pdf)" [IPDPS 2010] which is performing really well.

But what about updates? I couldn't produce a technique which can update the shortest paths quickly when the weight of an edge changes. On researching, I came across a paper "[On Dynamic Shortest Path problems](http://u.cs.biu.ac.il/~liamr/papers/OnDynamicShortestPath.pdf)", which states that

> Reductions that show that the incremental and decremental single-source
> shortest-paths problems, for weighted directed or undirected
> graphs, are, in a strong sense, at least as hard as the static all-pairs
> shortest-paths problem.

So the question is: **Are there useful heuristic approaches to solve this problem?**

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: I think that it is unfair to say “On researching through many papers finally concluded with …” without acknowledging the [answer](http://cstheory.stackexchange.com/a/9814/567) you received in your previous question which gave the reference to exactly the same paper.  
> **username_2**: The here link is to **this** question instead of the other. :-/  
> **username_3**: Edited for clarity and grammar; fixed broken link to previous answer.  
> **username_4**: Perhaps this paper can help you: http://db.csail.mit.edu/pubs/cq_icde_cr.pdf  

---

## 2 answers

### Answer by username_5 on 2012-02-01. Score: 1

your question seems quite advanced and it seems unlikely anyone has considered the incremental problem for the particular algorithm you are implementing when the new nonincremental algorithm was published by Yanagisawa as recently as 2010.

the algorithm you cite is apparently designed to be parallelizable therefore that seems like the 1st approach to optimizing it. ie implement it in a highly parallel implementation and just recompute all paths.

I have not seen a paper describing this, but how about this approach which seems to work in theory & in general but details could be tricky (maybe it appears in a paper somewhere-- would be interested if anyone has seen a similar technique). every algorithm to solve the problem must basically reduce to a (2-way?) comparison of edge weights. the resulting paths are built out of the results of these comparisons. the "comparison tree" for every optimal path can be stored during the 1st computation of all pairs.

then when any weights are changed, traverse through all prior stored/built-up comparison trees to recompute the answer. probably, for small changes, one would not have to descend "deeply" into those trees because the results of some or "many" prior comparisons are unchanged. one may have to modify the trees if new "comparison paths" in the trees are triggered but again this might not be expensive. however there would be a threshold where it is simpler to recompute everything from scratch when there are too many weight changes.

the main question of course is the memory cost of storing all the comparison trees.

(fineprint: and if all this actually worked, it would likely be a significant advance & publishable result.)


---

### Answer by username_6 on 2012-01-31. Score: -1

And in what kinds of updates are you interested? Both weight increase and decrease? Obviously, it should not be hard to solve edge increases since such an update influences only those optimal paths containing the changed edge and it is not hard to recomputed them quickly (actually, it can be done even more efficiently). Weight decrease is harder case but it does not make sense in route planning practice (usually).

Anyway, if you are already using some route planning (all pairs shortest path) approach, you should look for its "dynamization". I would not consider heuristics since I am not aware of any good heuristic route planning algorithm.

So what kind of updates are we talking about?

> **Comments:**
> **username_0**: Hello,Thanks for the reply.By updates I mean, both the increase & decrease. Basically every road has a score, depending upon the traffic at that edge,the score can decrease and increase. So the algorithm needs to adapt so that it can provide the shortest path considering the updates in all the shortest paths it has already found rather than re-finding all pair shortest paths.Can you please explain/provide link for the update part, I mean how would it be effective for all pairs? Secondly from the second para, apart from all pairs shortest path approach, can there be any other effective approach  

---

