Data Structures and Algorithms: Weighted Graph Processing — Part 2: A*

In continuation to my last blog, this time around we’re going to discuss the A* algorithm. Last time around we saw about Dijkstra’s algorithm and I mentioned that A* is similar to Dijkstra with only a slight but crucial twist to its approach.

Note

If you need a recap on Dijkstra’s or if you’re new to weighted-graph processing algorithms, check out my last post on Dijkstra’s algorithm:

Data Structures and Algorithms: Weighted Graph Processing — Part 1: Dijkstra

So, if you’re wondering — What is the A* algorithm? Why is it preferred most of the time over Dijkstra’s algorithm? Let’s get started then!

A* is a path-finding algorithm based on weighted graphs. A* is also known as the best-first search algorithm or informed search algorithm. Given a starting node of a graph(usually a weighted-graph) it aims to find a path to the target node having the smallest cost ( the factors for the cost can vary from distance, time, or any sought of hindrances along the way and etc.,)

Let’s take a real-life example, you’re planning to move from place A to B. So, now you open a digital mapping service (like g-maps for example), you would have noticed that there are multiple paths from source to destination and the best path is pointed out in reference to the estimated time of travel. Although there may be some paths that are shorter in distance but due to other factors such as traffic and speed limit, you might have been recommended another path as the best option.

So, now let’s connect this example with our base concept the road network is the graph, and the location such as a landmark, are the nodes, the various roads which connect the locations are the edges in the graph, distance, speed limit, or any other factor which may hinder the travel is considered as the weight along the path. So, the digital mapping service uses a path-finding algorithm such as the A* algorithm will find the best possible path from the starting point to the destination.

I hope we have some basic intuition on a path-finding algorithm so that now we can jump to the topic of the hour A* algorithm.

Basic terminology

Before looking into the algorithm, let’s first get familiar with some basic terminologies related to the A* algorithm:

1. Open list: It is a collection of all generated nodes, i.e., those are the nodes that were neighbors of expanded nodes. (The open list is often implemented as a priority queue so that algorithm can easily dequeue the next best node.)
2. Closed list: It is a collection of all expanded noes, i.e., those are the nodes that were already searched. This prevents the algorithm from revisiting the nodes.
3. A* algorithm has 3 parameters:

a) g: the cost of moving from the initial node to the current node. Basically, it is the same as all the nodes that have been visited since leaving the first node.

b) h: also known as the heuristic value, it the estimated cost of moving from the current node to the final node. The actual cost can’t be calculated until the final node is reached. Hence, h is the estimated cost. We must make sure that there is never an overestimation of the cost.

c) f: It is the sum of g and h. So, f = g + h.

Algorithm

1. Define the open list and initialize it with the start node.
2. Define the closed list.
3. If the open list is empty, return failure and exit.
4. Remove node n with the smallest value of f from open and move it to the closed list, if the n is the target node, return success and exit.
5. Expand node n.
6. If any successor to n is the target node, return success and the shortest path by tracing the path from the target node to the start node.
7. Else, for each successor node,

a) Apply the evaluation function f to the node

b) If the node has not been in either list, add it to the open list.

Note

The code implementation that we’re going to discuss is going to be in java (as I’m more comfortable with java 😅), but don’t worry I have given a pseudo code for the same algorithm below, which you could refer to implement the algorithm of the language of your choice.

Pseudo Code

Code

We’re going to try to implement A* algorithm for the weighted graph, given below:

We’re using an adjacency list to represent the graph, where each element in the list will have two values. One is the other node to which the node is connected with and the other is the weight along with the edge passing between the two nodes.

So, the output of the above program can be seen below which is 0->1->3->4 ->5

Applications

A* is often used for the common pathfinding problem in applications such as video games but was originally designed as a general graph traversal algorithm. It finds applications in diverse problems, including the problem of parsing using stochastic grammars in NLP. Other cases include an informational search with online learning.

So, we have come to the end of this post, and thank you so much 😊 if you have made it this far into this post. I will see you in the next post! Always grateful, never complacent!

References

1. http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
2. https://www.algorithms-and-technologies.com/a_star/java
3. https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Graphs/A_Star.java
4. https://www.educative.io/edpresso/what-is-the-a-star-algorithm
5. https://en.wikipedia.org/wiki/A*_search_algorithm
6. https://stackabuse.com/graphs-in-java-a-star-algorithm/
7. https://stackoverflow.com/questions/45577114/a-star-algorithm-open-and-closed-lists/45577852
8. https://www.gatevidyalay.com/tag/a-algorithm-applications/
9. https://www.researchgate.net/figure/A-search-algorithm-Pseudocode-of-the-A-search-algorithm-operating-with-open-and-closed_fig8_232085273

My Github Repository

1. https://github.com/Sethuram52001/DSA