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
