Edge-weight updates in all pair shortest path problem 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 led me to Hiroki Yanagisawa's paper "A multi-source label-correcting algorithm for the all-pairs shortest paths problem" [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", 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?
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 &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. 

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 &amp; publishable result.)