Pathfinding on a grid while blocking cells online

Question

Suppose we have a N*N grid with start and end points A and B, and we're given K < N^2 queries online telling us to block a cell on the grid. We want to find and output the shortest path between A and B after each query.

Is there a better solution to this than to recalculate the shortest path after each query (or if not, proof that there isn't)? Since the grid only changes one cell at a time, it feels like there must be some way to make use of information from previous queries without starting from scratch each time.

Answer 1

If the cell that is blocked is NOT on the shortest path, then the shortest path is not changed - doesn't need to be recalculated.

- Calculate shortest path

* Cell X is blocked

- LOOP C over cells in shortest path
   IF C == X
      recalculate shortest path
      Break from loop C

Here is a faster algorithm, if you are content with an approximate shortest path:

- Calculate shortest path
- Set approxCount = 0

* Cell X is blocked

- LOOP C over cells in shortest path
   IF C == X
      - IF approxCount < small arbitrary integer
            - Calculate path from previous cell to C to cell after C in path
            - Insert path around block
            - Increment approxCount
     - ELSE
            - recalculate shortest path
            - Set approxCount = 0
     - Break from loop C

The small arbitrary integer should be set to a value that gives you approximations that you can tolerate.

The path calculation around the block should be based on a breadth first search so it can be stoppped quickly when a path is found.