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

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

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_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    "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

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