HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

How is A* search superior to Dijkstra's algorithm

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
dijkstrasearchalgorithmhowsuperior

Problem

Dijkstra's algorithm is often quoted as being used to find the shortest path route however I was surprised to know that there exist A* search which is a extension of Dijkstra's algorithm.

How is it that A* search algorithm is able to perform better compared to Dijkstra's algorithm , what sort of technique does it used that Dijkstra's algorithm did not use ???

Solution

Consider providing driving directions from an origin to a destination. Although sometimes traveling away from the destination for short distances is required (think highway on ramp), in general it is best to travel toward the destination. In this case A* is likely to outperform Dijkstra's algorithm because it (probably) will traverse less of the graph.

Dijkstra's algorithm uses a single heuristic, $g(n)$, which is the distance from the origin. In selecting the next road to evaluate, the road with the least $g(n)$ is selected; however, this road may travel away from the destination. A adds an estimate of the remaining distance, $h(n)$, to bias the search towards the destination. The full A heuristic is $f(n) = g(n) + h(n)$. Note that as the search progresses, $f(n)$ must monotonically increase or else the path found may not be the shortest. Thus, $h(n)$ must be optimistic and never underestimate the remaining distance (in the directions example, assume the remainder of the trip can be a straight line).

Context

StackExchange Computer Science Q#23619, answer score: 4

Revisions (0)

No revisions yet.