A line-by-line breakdown of the A* Python script and its connection to the algorithm's core concepts.
Prepared by Sajjad Ahmed Niloy
The graph dictionary represents the physical map of nodes and the actual cost to travel between them. The heuristics dictionary is our h(n) function—the estimated cost (our "gut feeling") from a node to the goal.
This dictionary stores g(n), the cost of the cheapest path found *so far* from the start node to node n. We initialize all costs to infinity and the start node's cost to 0.
Think of this as a to-do list of intersections to visit. It's a special list (a priority queue) that always keeps the most promising location—the one with the lowest f(n) score—right at the top, ready to be picked next.
This is a list of intersections we've already fully explored. By keeping track of where we've been, we avoid going in circles or re-doing work.
The main loop continues as long as our to-do list (open_set) isn't empty. If we run out of places to check before reaching the goal, it means there's no possible path.
This is the "smart" step. We don't just pick a random spot. We look at the total estimated cost (f-score) for every spot on our list and pick the one with the lowest value. This is our best bet for the next step.
The first thing we do is check if this "best spot" is actually our final destination. Because A* is so good at picking the most promising path, the very first time we pick the goal node, we know we've found the fastest route. Mission accomplished!
Now that we're at a new intersection, we look at our map (graph) to see all the directly connected roads (neighbor) and how long it takes to go down each one (cost).
This is where the algorithm learns and finds shortcuts.
# 'heapq' is a Python library that gives us a "priority queue". # Think of it as a magical to-do list that always keeps the # item with the lowest score at the top, ready to be grabbed. import heapq # This defines our "recipe" for the A* search. It needs a map (graph), # a start point, a goal, and the gut-feeling estimates (heuristics). def a_star_search(graph, start, goal, heuristics): # First, create a master list of every single location on the map # to make sure our score sheet is complete. all_nodes = set(graph.keys()) for node in graph: all_nodes.update(graph[node].keys()) # Create a score sheet for the 'g_score' (actual travel time from start). # At the beginning, we don't know how to get anywhere, so all scores are infinity. g_scores = {node: float('inf') for node in all_nodes} # The time to get to the start node from itself is zero. g_scores[start] = 0 # This is our "visited" list, for places we've already fully explored. closed_set = set() # This is our main to-do list ('open_set'). It starts with only one item: # our starting node. Each item contains: (f-score, g-score, node_name, path). open_set = [(heuristics[start], 0, start, [start])] # This loop is the engine of the algorithm. It keeps running as long # as there are items on our to-do list. while open_set: # Grab the most promising item (lowest f-score) from the to-do list. f_score, g_score, current_node, path = heapq.heappop(open_set) # Check if we've arrived at the goal. If so, we're done! if current_node == goal: return path, g_score # If we've already found a better path to this node, skip this one. if g_score > g_scores[current_node]: continue # Add the current spot to our "visited" list so we don't come back. closed_set.add(current_node) # Now, look at all the neighbors of the current node. if current_node in graph: for neighbor, cost in graph[current_node].items(): # If we've already visited this neighbor, ignore it. if neighbor in closed_set: continue # Calculate the travel time to this neighbor through the current node. tentative_g_score = g_score + cost # Check if this new path is a shortcut. if tentative_g_score < g_scores[neighbor]: # It IS a shortcut! Update our records. g_scores[neighbor] = tentative_g_score h_score = heuristics.get(neighbor, 0) f_score = tentative_g_score + h_score new_path = path + [neighbor] # Add the neighbor to our to-do list with its new, better score. heapq.heappush(open_set, (f_score, tentative_g_score, neighbor, new_path)) # If the to-do list becomes empty and we never found the goal, no path exists. return None, None # --- This is where the script starts running --- if __name__ == "__main__": # The map of intersections and travel times. graph = { 'S': {'B': 1, 'C': 4}, 'B': {'D': 3, 'C': 2}, 'C': {'E': 5}, 'D': {'F': 2, 'W': 4}, 'E': {'W': 3}, 'F': {'W': 1} } # The list of gut-feeling estimates for each node. heuristics = { 'S': 6, 'B': 5, 'C': 8, 'D': 2, 'E': 5, 'F': 1, 'W': 0 } start_node = 'S' goal_node = 'W' # Call our recipe and store the results. path, cost = a_star_search(graph, start_node, goal_node, heuristics) # Print the final answer. print(f"Path: {path}, Cost: {cost}")
Copy the complete script above and save it in a file. Let's name it:
Open a terminal or command prompt and navigate to the directory where you saved the file.
Type the following command and press Enter:
The script will run the A* search on the example graph and print the result. You should see the following output in your terminal.