www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - [OT] Pathfinding algorithm

reply "rasmus svensson" <rasmus.svensson linux.nu> writes:
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?
Sep 21 2013
next sibling parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
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).
Sep 21 2013
prev sibling next sibling parent reply "Gary Willoughby" <dev nomad.so> writes:
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
Sep 21 2013
parent Joseph Rushton Wakeling <joseph.wakeling webdrake.net> writes:
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.
Sep 21 2013
prev sibling parent "Ivan Kazmenko" <gassa mail.ru> writes:
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.
Sep 22 2013