Implementing A Search in Python

Understanding the A* formula is easier when it is applied to a working example.

In this lesson, you will implement A* to find a low-cost path through a small weighted graph.

Problem Setup

Consider the following connections:

2        3

A ------ B ------ D

\        \       /

4        2     2

\        \   /

C ------ E

3

The graph contains weighted connections. The algorithm must find a minimum-cost route from A to D.

For this example, use the following heuristic estimates:

These values are illustrative estimates. For an admissible heuristic, each estimate must not exceed the actual cheapest remaining cost.

Python Implementation

import heapq
graph = {
"A": {"B": 2, "C": 4},
"B": {"A": 2, "D": 3, "E": 2},
"C": {"A": 4, "E": 3},
"D": {"B": 3, "E": 2},
"E": {"B": 2, "C": 3, "D": 2}
}
heuristic = {
"A": 5,
"B": 3,
"C": 4,
"D": 0,
"E": 2
}
def a_star(graph, heuristic, start, goal):
priority_queue = [(heuristic[start], 0, start)]
came_from = {}
cost_so_far = {start: 0}
while priority_queue:
_, current_cost, current = heapq.heappop(priority_queue)
if current_cost != cost_so_far.get(current):
continue
if current == goal:
path = [goal]
while path[-1] != start:
path.append(came_from[path[-1]])
path.reverse()
return path, current_cost
for neighbor, edge_cost in graph[current].items():
new_cost = current_cost + edge_cost
if new_cost < cost_so_far.get(neighbor, float("inf")):
cost_so_far[neighbor] = new_cost
came_from[neighbor] = current
priority = new_cost + heuristic[neighbor]
heapq.heappush(
priority_queue,
(priority, new_cost, neighbor)
)
return None, float("inf")
path, cost = a_star(graph, heuristic, "A", "D")
print("Path:", path)
print("Total cost:", cost)

Expected Output

Path: ['A', 'B', 'D']

Total cost: 5

The route A → B → D has a total cost of (2+3=5).

The alternative route A → B → E → D costs (2+2+2=6), so it is more expensive.

Understanding the Implementation

• graph stores each node's neighbors and the associated edge costs.
• heuristic provides an estimate of the remaining cost to the goal.
• priority_queue selects the node with the lowest estimated total cost.
• cost_so_far records the best known cost of reaching each node.
• came_from records the preceding node so that the route can be reconstructed.
• new_cost calculates the accumulated cost of a possible route.
• The algorithm updates a node when it discovers a cheaper path.

The implementation also skips outdated priority-queue entries when a better route has already been found.

Important Implementation Notes

This example assumes a finite graph with non-negative edge costs and a suitable heuristic. A* optimality depends on the heuristic and the search implementation satisfying the relevant conditions.

For example, using (h(n)=0) for every node reduces A* to Uniform-Cost Search.

Practical Challenge

Modify the graph and find the cheapest path between A and E.

Then:

1. Change the edge cost between B and D.
2. Run the algorithm again.
3. Compare the original and updated routes.
4. Explain how the accumulated cost affects the selected path.