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?

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

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?

Maybe i'm wrong but i'm assuming you are pre-calculating the shortest paths from each node to all others is because you intend to traverse a path at some point in the future? The problem with this approach is that if a node is marked as impassable then you have to again do a lot of pre-calculation for every node it affects. Not only that but to avoid re-calculating them *all* you need to use an algorithm to find which are affected before you even start recalculating? To me this seems like too much work and could probably be solved by thinking a little differently.

Try implementing the A* algorithm which will give you a path from A to B *without* calculating paths to and from every node. Also if a node is marked impassable (even while running) you can just restart the algorithm from where you are back to B.

This sounds really scary stuff but A* is actually quite straightforward if you can find a nice resource to describe how it works.

Like these:
http://www.policyalmanac.org/games/aStarTutorial.htm
http://en.wikipedia.org/wiki/A*_search_algorithm

On 21/09/13 21:13, Gary Willoughby wrote:
> Maybe i'm wrong but i'm assuming you are pre-calculating the shortest paths from
> each node to all others is because you intend to traverse a path at some point
> in the future? The problem with this approach is that if a node is marked as
> impassable then you have to again do a lot of pre-calculation for every node it
> affects. Not only that but to avoid re-calculating them *all* you need to use an
> algorithm to find which are affected before you even start recalculating? To me
> this seems like too much work and could probably be solved by thinking a little
> differently.
>
> Try implementing the A* algorithm which will give you a path from A to B
> *without* calculating paths to and from every node. Also if a node is marked
> impassable (even while running) you can just restart the algorithm from where
> you are back to B.
>
> This sounds really scary stuff but A* is actually quite straightforward if you
> can find a nice resource to describe how it works.
>
> Like these:
> http://www.policyalmanac.org/games/aStarTutorial.htm
> http://en.wikipedia.org/wiki/A*_search_algorithm

Good advice, but bear in mind that there may be a very good reason to want to know the shortest path between _every_ pair of nodes.

Example: you calculate the closeness centrality for every vertex (which involves knowing the shortest path between every pair of vertices).  Now you knock out one vertex and you want to recalculate the closeness centrality values -- but ideally you'd like to avoid doing the whole calculation from scratch.  So, you need to store the shortest paths from the first calculation and dynamically update them to work out which nodes' centrality values need updating.

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.