A* search algorithm is a path finding algorithm that finds the single-pair shortest path between the start node(source) and the target node(destination) of a weighted graph.
Asearch algorithm is a path finding algorithm that finds the single-pair shortest path between the start node(source) and the target node(destination) of a weighted graph. The algorithm not only considers the actual cost from the start node to the current node(g) but also tries to estimate the cost will take from the current node to the target node using heuristics (h). Then it selects the node that has the lowest f-value(f=g+h) to be the next node to move until it hits the target node. Dijkstra's algorithm is a special case of A algorithm where heuristic is 0 for all nodes.
![A Star Search](https://miro.medium.com/v2/resize:fit:875/1*QvF-25wEHhQiWowGeJ8JjQ.png)
How A* Algorithm Works?
The formula for A* algorithm considers two functions, g(n) and h(n). Imagine that we are currently at node n, g(n) tells us the actual cost we took from the start node to the current node. h(n) is a heuristic function that estimates the cost we will take to get to the target node from the current node. Therefore, h(n) is an educated guess and it is crucial to determine the performance of A* algorithm. Based on the sum of the g(n) and h(n), f(n), the algorithm is able to estimate the total cost from the start node to the end node.
f(n) = g(n) + h(n) , f(n): the estimate of the total cost from start node to target node through node n
g(n): actual cost from start node to node n
h(n): estimated cost from node n to target node
The algorithm selects the minimum f-value node as the next current node to explore and continuously update g(n) and h(n) if a better path is found for nodes it encountered. This process continues until the algorithm reaches the target node.
A* algorithm vs. Dijkstra's algorithm
A* Algorithm only finds the shortest path between the start node and the target node, whereas Dijkstra's algorithm finds the shortest path from the start node to all other nodes because every node in a graph is a target node for it.
A* algorithm runs faster than Dijkstra's algorithm because it uses a heuristic to direct in the correct direction towards the target node. However, Dijkstra's algorithm expands evenly in all of the different available directions because it has no knowledge regarding the target node before hand, it always processes the node that is the closest to the start node based on the cost or distance it already took.
![A* algorithm vs. Dijkstra's algorithm](https://miro.medium.com/v2/resize:fit:875/1*FzCo76pN8UJt2kIeOFlCzA.png)
Graphical Explanation
Heuristic is crucial to the performance of A* algorithm. The heuristic function we use here just for the demo purpose.
![graph example](https://miro.medium.com/v2/resize:fit:875/1*5UTGfoZLPUA9dXJ_v_CsWg.png)
- Step 1
- a: Set the distance to the start node itself to 0 and the distance to all other nodes to infinity.
- b: Calculate the f value for the start node and set the previous node to none/nil/null.
- c: Initialize an open list and close list which are empty initially.
![step 1](https://miro.medium.com/v2/resize:fit:875/1*W6CaGse0EnoDi5RNW7Kb1g.png)
- Step 2: Place the start node into the open list
![step 2](https://miro.medium.com/v2/resize:fit:875/1*MJwjLSxWe_n1yW7rxkuu7w.png)
- _Step 3
_*-* a*:* Find the node with the minimum f-value in the open list and removed from the list. Denote this node as the current node.
- b: Check if the current node is the target node or not
- c: Populate all the current node's neighboring nodes and do following checks for each neighboring nodes
1. Is the neighboring node in the close list?
- Yes. Skip this node.
- No. Go to 2.2. Calculate g value for the neighboring node and check if a better
path(lower g value) is found? - No, Skip this node - Yes. Go to 3.3. Calculate g, h and f value for the neighboring node and set
the previous node to the current node**4. Check if the neighbor node in the open list?** - Yes. Update g, h and f value of the neighboring node in the
open list - No. Insert this neighboring node to the open list
- d: Place the current node to the close list because we have expanded this node.
![step 3](https://miro.medium.com/v2/resize:fit:875/1*ALCIZaJVV_iZ22aJDn8KwA.png)
- Step 4: Repeat Step 3 until reaches the target node
demo iteration 1
![iteration 1–1](https://miro.medium.com/v2/resize:fit:875/1*3daYK311AZ5EhMZ7SlfMyA.png)
![iteration 1–2](https://miro.medium.com/v2/resize:fit:875/1*yxdTd3QM0kQiZ-Xa5Rdinw.png)
![iteration 1–3](https://miro.medium.com/v2/resize:fit:875/1*bs4TplpOIkxhzx_3TKv7-A.png)
demo iteration 2
![iteration 2–1](https://miro.medium.com/v2/resize:fit:875/1*eX758M4Z1pHgXiVf2Re1pQ.png)
![iteration 2–2](https://miro.medium.com/v2/resize:fit:875/1*8qG-dpRBcGksbFNUql6cLg.png)
![iteration 2–3](https://miro.medium.com/v2/resize:fit:875/1*wGwIDY1BdPU4fLYd03E_tw.png)
demo iteration 3
![iteration 3–1](https://miro.medium.com/v2/resize:fit:875/1*WEIx9GyNjStRCgMmd08ksg.png)
![iteration 3–2](https://miro.medium.com/v2/resize:fit:875/1*1o9QqFM6kjeVRD96Wzk_wg.png)
![iteration 3–3](https://miro.medium.com/v2/resize:fit:875/1*AEvC7BRbwoY7OBXwbIGk4A.png)
demo iteration 4
![iteration 4–1](https://miro.medium.com/v2/resize:fit:875/1*nOouyfpxSOaOOP2nuL9TAA.png)
![iteration 4–2](https://miro.medium.com/v2/resize:fit:875/1*xzenBGkWstsSNEoNtGBHmQ.png)
![iteration 4–3](https://miro.medium.com/v2/resize:fit:875/1*N3nVtRAcjclt4DRBSLnkSQ.png)
demo iteration 5
![iteration 5–1](https://miro.medium.com/v2/resize:fit:875/1*LfoBualez23-DK5xMWJ7zQ.png)
final result
![](https://miro.medium.com/v2/resize:fit:875/1*L6s9xmzwxjWjOEe-tvTPKg.png)
At the end, we can backtrack the shortest path using the previous node. In this demo, we use A* algorithm to search the shortest path without necessarily search all the graph.(We haven't examined node 4 yet, so you can see the node 4 is till on the open list). Unlike Dijkstra's algorithm, it has to expand all the nodes in the graph.
You can check here to know more about Dijkstra's algorithm.
Code Implementation
Data Structure
Use Priority queue to get the lowest f-value node for each run. In this demo, we implement code using min heap data structure .
Complexity
Time: O(nlog(n)), Space: O(n)
n: the total number of nodes in the graph
Pseudocode
initialize a min Heap contains the start node
minHeap = MinHeap([start])While minHeap is not empty:
grab the minimum f-value node from minHeap and denote as current
current = minHeap.pop() # check if current is the target node
if current == target:
break
populate all current node's neighbors
for neighbor in current.neighbors:
compute neighbor's g, h, f value
Python
- code
- min heap