[OT] Pathfinding algorithm

[Joseph Rushton Wakeling]

On 21/09/13 17:48, 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?

This is on the basis of a very quick internet search, but the following may be 
useful for you:
http://informatica.ing.univaq.it/dangelo/presentations/iccta-2007.pdf
http://stackoverflow.com/questions/6760163/dynamically-updating-shortest-paths
http://www.dis.uniroma1.it/~demetres/docs/dapsp-full.pdf

Assuming that you actually have _all shortest paths_ calculated, then you 
probably need some kind of data structure that gives you an easy (i.e. O(1)) way 
to identify which paths a given node belongs to (should be possible to set up as 
part of your first calculation of all the shortest paths).  Then, you simply 
need to take those paths that the deleted node belongs to, and recalculate them.

On the basis of my quick search, the 3rd link above looks promising (and has a 
bunch of references to previous literature).