I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles.
My goal is to output a map, based on given location on the grid, with the shortest path to all the cells on the grid, some thing like this:
4 3 2 3
3 2 1 2
4 x x 3
5 6 5 4
The starting position is at node with the weight of 1. X represent the obstacles.
I achieve this goal using Breadth-first-search. My question is how can I reduce the cost of the next search if:
Only my location on the grid is changed, and/or,
if only the location of the obstacles is changes and/or
if both my location and the location of the obstacles is changed.
As for now I perform full recalculation in all those cases.