[OT] Pathfinding algorithm

[Ivan Kazmenko]

On Saturday, 21 September 2013 at 15:49:00 UTC, rasmus svensson 
wrote:
> Assuming the shortest path from from all nodes to every other 
> node is already pre-computed:
>
> What is a fast algorithm to update all paths, if one node is 
> marked as inpassible.
>
> Any good 3rd party library or research paper out there?

A short note on worst case complexity.  In a star graph, if you 
remove the central vertex, *all* paths between pairs of other 
vertices are affected (they become pairwise unreachable).  So, if 
there is a way to do it in less than V^2, it will at least have 
to store paths in some sophisticated way, better than just a VxV 
matrix with one element for each path.

Ivan Kazmenko.