[csom]

Data structures called "distance oracles" handle such problems. However, most research results are for static graphs only.

If the graphs are grids (as in the cstheory.stackexchange.com question) they are planar and some dynamic data structures exist (unclear whether the constants are small enough for the application in question):

Exact shortest paths:

Jittat Fakcharoenphol, Satish Rao: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci. 72(5): 868-889 (2006)

Approximate shortest paths:

Philip N. Klein, Sairam Subramanian: A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC 2012: 1199-1218