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).
