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?