I have a graph with computed distances from the "start" node. Now I'd like to remove one node (except the starting one) and recompute distances (ideally without running Shortest Path First on the whole graph).

I don't know how to google such an algorithm and my attempts seem to be quite complicated (especially when compared to adding a new node).