9 ms·

Reweighting a graph for faster shortest paths

52 points by mc 15y ago

vecter 15y ago
When I was taught A*, I was just given the mathematical definition of admissible and left to run with that. The intuition the author gave transforms some vague notion of a weight function with certain properties into an almost obvious mental picture. I wish more things were taught this way at school.
repsilat 15y ago
One point this article skips over is that Dijkstra's algorithm can be used more generally to find a shortest paths tree to all destinations, whereas A* is really just a single-source, single-destination pathfinding algorithm. Adding the heuristic obviously gets you to termination faster, but the work done by Dijkstra's algorithm isn't wasted if you're actually going to use it later.
ot 15y ago
These slides summarize pretty much all the recent developments in shortest path algorithms: http://research.microsoft.com/en-us/people/goldberg/erice.pdf http://research.microsoft.com/en-us/people/goldberg/erice.pd... There are example with maps overlaid with the nodes visited by each algorithm before finding the solution. The difference between Dijkstra, A* and landmarks-based algorithms is impressive!
Sharlin 15y ago
Another useful way to see A* is as the synthesis of two different search algorithms. To compute which untraversed node to choose next, A* uses the function f(n) = g(n) + h(n) where g(n) is the actual traversed distance from the start to n, and h(n) is an (optimistic) approximation of the distance from n to the goal. Now, without making any other modifications to the algorithm, if we substitute g(n) = 0 what we get is the greedy "best-first" search [1]. If, on the other hand, we select h(n) = 0 we get a single-goal variant of Dijkstra's algorithm [2]. [1] http://en.wikipedia.org/wiki/Best-first_search http://en.wikipedia.org/wiki/Best-first_search [2] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
suivix 15y ago
It's funny how he posted it on Livejournal. Talk about a dead site.

52 points by mc 15y ago

When I was taught A*, I was just given the mathematical definition of admissible and left to run with that. The intuition the author gave transforms some vague notion of a weight function with certain properties into an almost obvious mental picture. I wish more things were taught this way at school.

repsilat 15y ago

One point this article skips over is that Dijkstra's algorithm can be used more generally to find a shortest paths tree to all destinations, whereas A* is really just a single-source, single-destination pathfinding algorithm. Adding the heuristic obviously gets you to termination faster, but the work done by Dijkstra's algorithm isn't wasted if you're actually going to use it later.

ot 15y ago

These slides summarize pretty much all the recent developments in shortest path algorithms: http://research.microsoft.com/en-us/people/goldberg/erice.pdf http://research.microsoft.com/en-us/people/goldberg/erice.pd... There are example with maps overlaid with the nodes visited by each algorithm before finding the solution. The difference between Dijkstra, A* and landmarks-based algorithms is impressive!

Sharlin 15y ago

Another useful way to see A* is as the synthesis of two different search algorithms. To compute which untraversed node to choose next, A* uses the function f(n) = g(n) + h(n) where g(n) is the actual traversed distance from the start to n, and h(n) is an (optimistic) approximation of the distance from n to the goal. Now, without making any other modifications to the algorithm, if we substitute g(n) = 0 what we get is the greedy "best-first" search [1]. If, on the other hand, we select h(n) = 0 we get a single-goal variant of Dijkstra's algorithm [2]. [1] http://en.wikipedia.org/wiki/Best-first_search http://en.wikipedia.org/wiki/Best-first_search [2] http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

suivix 15y ago

It's funny how he posted it on Livejournal. Talk about a dead site.