Is there a way to reflect small edge-weight changes after computing Floyd-Warshall on a large graph?

Question

I am working on a hex-based game in which I'm trying to pre-calculate pathfinding for a given map using the Floyd-Warshall algorithm. The map size is on the order of thousands of hexes (so maximum tens of thousands of edges).

The map represents an arena in which two teams fight, and both have the ability to change the map, either by creating complete walls (removing a vertex from the graph), or changing weights on the edges (i.e. by temporarily making a hex difficult to walk over).

The reason I'm considering using all-pairs-shortest-path algorithm is because I need to simulate the game as fast as possible, and thus I can't waste time with actual pathfinding during the simulation.

Is there a way to detect which paths need to be re-calculated when a change is made to the graph? It seems that if I only increased the weights/removed vertices, I could only re-calculate the affected paths, is that true? And what if I'm also decreasing weights/adding new vertices/edges?

Answer 1

Yes. The phrase to search for in the literature is "dynamic shortest paths". "Dynamic" refers to the path that the graph might change, and we want to efficiently update the shortest paths (more efficiently than recomputing them from scratch).

There are different ways one might change the graph. Some papers consider the case where edges can be added. Others consider where edges can be removed. You can also find algorithms that can handle both kinds of changes; that might go under the name "fully dynamic shortest paths".

Search the literature. You'll find many algorithms, with different tradeoffs between running time, simplicity of implementation, and types of graph updates supported.