Unlocking the Steps of A*: A Step-by-Step Guide + Python code (part 2)

You can access Part 1 here. The first part explains how to solve the shortest path problem using the popular Dijkstra algorithm and provides code examples.

A*

Unlike Dijkstra’s algorithm, which explores all possible paths from the start node, the A* algorithm estimates the cost of the remaining path from the current node to the goal node using a heuristic function. The heuristic function is a way to make an educated guess about how far a current node is from the goal node, based on some known or estimated information. For example, if you are trying to find the shortest path between two cities, you might estimate the distance based on the straight-line distance between them or the average time it takes to travel between them.

By using a heuristic function, the A* algorithm can prioritize exploring the most promising paths toward the goal node instead of exploring all possible paths. This makes the algorithm faster and more efficient, especially when dealing with large or complex maps or graphs. We will see more detail about a heuristic function with the same example as Part 1.

Example:
We have a starting node A, depicted by the color yellow, and we want to find the shortest path to the goal node H, depicted in the color green.

Figure 1. Example of the graph

To solve this example with the A* algorithm, we need to define the heuristic function. In this case, we choose the total of the remaining edges from the starting node to the goal node as the heuristic function. Now, we will solve the problem with the following steps:

Step 1 -> | A
Explanation: Start with initial node A.

Step 2 -> A | B(A,1+3) C(A,2+2)
Explanation: We find the unvisited neighbors of node A, which are B and C, and put them to the right of the vertical line ‘|’. The values inside the parentheses represent the previous node and the cost to the neighbor node from initial node A plus the remaining edges from the neighbor node to the goal node. For example, if we have three remaining edges from node B to node H, which are B->D, D->G, and G->H, we add the total of the remaining edges inside node B. Similarly, if we have two remaining edges from node C to node H, which are C->E and E->H, we add the fewest remaining edges from the chosen node to the goal node. Finally, we put the previous node, which is A, to the left of ‘|’.

Figure 2. Illustration of A | B(A,1+3) C(A,2+2)

Step 3 -> A B | C(A,2+2) D(B,3+2)
Explanation: Even though nodes B and C have the same cost value, we will choose node B as the next node because it has a lower cost to the neighbor compared to node C. Then we check the unvisited neighbor of node B, which is D, and put it to the right of the vertical line ‘|’. We have two remaining edges from node D to node H, which are D->G and G->H. Then we add the total of the remaining edges inside node D. Finally, we move the previous node, B, to the left of the '|' symbol.

Figure 3. Illustration of A B | C(A,2+2) D(B,3+2)

Step 3 -> A B C | D(B,3+2) E(C,3+1) F(C,4+1)
Explanation: We will choose node C as the next node because it has the lowest cost compared to the other nodes. Next, we locate node C's unvisited neighbors, E and F, and place them to the right of the vertical line '|'. Calculate the remaining edges from nodes E and F to node H, and add them inside the parentheses of both nodes. Finally, we move the previous node, C, to the left of the ‘|’ symbol.

Figure 4. Illustration of A B C | E(C,3+1) D(B,3+2) F(C,4+1)

Step 4 -> A B C E | D(B,3+2) F(C,4+1) H(E,6+0)
Explanation: We will choose node E as the next node because it has the lowest cost compared to the other nodes. Next, we locate node E’s unvisited neighbors, G and H. Drop G because we can directly reach to the goal from node E. Then, place H to the right of the vertical line ‘|’. We don’t need to calculate the remaining edge from node E to node H because the value is absolutely zero. Finally, we move the previous node, E, to the left of the ‘|’ symbol.

Figure 5. Illustration of A B C E | D(B,3+2) F(C,4+1) H(E,6+0)

Step 5 -> A B C E F | D(B,3+2) H(F,5)
Explanation: Omit node H because it is the goal. Then we will choose node F as the next node because it has the lowest cost compared to the other nodes. Next, we locate node F’s unvisited neighbor, H. Then, place H to the right of the vertical line ‘|’. We don’t need to calculate the remaining edge from node E to node H because the value is absolutely zero. Finally, we move the previous node, F, to the left of the ‘|’ symbol.

Figure 6. Illustration of A B C E F | D(B,3+2) H(F,5)

Step 6-> Choose the shortest path
We know that the shortest path to node H comes from node F because it has a lower cost compared to node E. We don’t need to calculate the cost from node D to node H because the cost will be at least 5, which means it will not give a more optimal solution. Last, we can trace back the previous nodes of node F until we reach the initial node A. The shortest path is A -> C -> F -> H.

Figure 6. The shortest path

The advantages of A* over Dijkstra
Do you realize how many steps we need to take to solve the shortest distance problem with A*?

In fact, the A* algorithm can solve this problem in as few as six steps, while Dijkstra’s algorithm requires nine steps to solve the same problem. This efficiency is made possible by the heuristic function used in A*, which allows for a guided-search approach that can quickly identify the most promising paths to explore. This makes A* a highly effective algorithm for solving a wide range of shortest-path problems, from navigation to logistics and beyond.

Python Code

In order to use the A* algorithm in Python, the initial step is to establish the graph. To accomplish this, a file named graph.csv can be utilized, which is displayed in Figure 3 and contains the representation of the graph. The file contains rows that display a specific edge, including the starting node, its neighbor node, and the cost associated with traveling from the starting node to the neighbor node.

A,B,1
A,C,2
B,D,2
C,D,1
C,E,1
C,F,2
D,G,1
F,E,1
F,H,1
E,G,1
E,H,3
G,H,3

To obtain the representation of the graph shown in graph.csv, a function called read_graph_from_csv() needs to be created. If we run the code below, we will get the representation of the graph as follows:

import csv

def read_graph_from_csv(filename):
    graph = {}
    with open(filename) as f:
        reader = csv.reader(f)
        for u, v, w in reader:
            if u not in graph:
                graph[u] = []
            if v not in graph:
                graph[v] = []
            graph[u].append((v, int(w)))
            graph[v].append((u, int(w)))
    return graph

graph = read_graph_from_csv('graph.csv')
graph

Output:
{'A': [('B', 1), ('C', 2)],
 'B': [('A', 1), ('D', 2)],
 'C': [('A', 2), ('D', 1), ('E', 1), ('F', 2)],
 'D': [('B', 2), ('C', 1), ('G', 1)],
 'E': [('C', 1), ('F', 1), ('G', 1), ('H', 3)],
 'F': [('C', 2), ('E', 1), ('H', 1)],
 'G': [('D', 1), ('E', 1), ('H', 3)],
 'H': [('F', 1), ('E', 3), ('G', 3)]}

Create a function A_star() with the input of the graph, the starting node, and the goal node. This function will produce the travel distances with the nodes it visits.

def heuristic(node, goal, graph):
    remaining_edges = 0
    for neighbor, weight in graph[node]:
        if neighbor != goal:
            remaining_edges += 1
    return remaining_edges

def a_star(graph, start, goal, heuristic):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    unvisited = set(graph.keys())
    previous = {node: None for node in graph}
    current = start
    while unvisited:
        for neighbor, weight in graph[current]:
            new_dist = distances[current] + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                previous[neighbor] = current
        unvisited.remove(current)
        if current == goal:
            break
        candidates = {node: distances[node] + heuristic(node, goal, graph) for node in unvisited}
        current = min(candidates, key=candidates.get)
    return distances, previous

def shortest_path(previous, start, goal):
    node = goal
    path = [node]
    while node != start:
        node = previous[node]
        path.append(node)
    path.reverse()
    return path

graph = read_graph_from_csv('graph.csv')

start = 'A'
goal = 'H'

distances, previous = a_star(graph, start, goal, heuristic=lambda node, goal=goal, graph=graph: heuristic(node, goal, graph))
path = shortest_path(previous, start, goal)
print("Shortest path from node {} to node {}: {}".format(start, goal, path))

Shortest path from node A to node H: ['A', 'C', 'F', 'H']

If you have read this sentence, it means that you have successfully used A*’s algorithm to find the shortest path! Congratulations.