## digitalmars.D.learn - [OT] Pathfinding algorithm

- rasmus svensson (5/5) Sep 21 2013 Assuming the shortest path from from all nodes to every other
- Joseph Rushton Wakeling (13/17) Sep 21 2013 This is on the basis of a very quick internet search, but the following ...
- Gary Willoughby (21/26) Sep 21 2013 Maybe i'm wrong but i'm assuming you are pre-calculating the
- Joseph Rushton Wakeling (9/26) Sep 21 2013 Good advice, but bear in mind that there may be a very good reason to wa...
- Ivan Kazmenko (9/14) Sep 22 2013 A short note on worst case complexity. In a star graph, if you

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

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

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

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_algorithmGood 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

On Saturday, 21 September 2013 at 15:49:00 UTC, rasmus svensson wrote:

Sep 22 2013