[OT] Pathfinding algorithm

[Joseph Rushton Wakeling]

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.