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.
