# How to reduce the cost of search based on previous BFS?

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.

• Look at A*, or better yet, incremental A* also known as D*. There are many variants of D* out there as well. (By the way, is your graph really $K$-regular? Your example doesn't look $K$-regular. At first, you say your graph is unweighted, but then you talk about a "node with weight of 1" and your picture seems to support this too. Can you edit accordingly?) – Juho Jun 10 '14 at 12:38
• @Juho my graph is indeed unweighted(May be except obstacles that I do not know how to refer them), the example is the desired output. Aren't D* is more expensive than BFS,O(N)? – Ilya Gazman Jun 11 '14 at 0:03