Finding the shortest distance in a dynamic graph
The search keywords are "dynamic all pairs shortest paths".

Demetrescu and Italiano have a good survey,
http://dl.acm.org/citation.cfm?id=1198519

Looks like $O(n^2 log^3 n)$ cost per update if you want to maintain fast lookups.