@arj yes. One observation is that when you remove an edge, paths can only stay the same or get longer. So nodes that are already closer than that node was cannot be affected. Only nodes followed by the removed node may be affected...

Update: turns out dynamic shortest paths is an open problem (now I don't feel so bad about not solving it) this stackoverflow thread links to various papers.