A* Search in Python

astar.py

import heapq

def estimated_distance(node, target):
    x1, y1 = node
    x2, y2 = target
    dx, dy = abs(x1 - x2), abs(y1 - y2)
    dist = dx + dy
    return dist

def shortest_path(graph, source, target, heuristic_func=None):
    visited = set()
    queue = [(0, 0, [source])]
    while queue:
        _, distance, path = heapq.heappop(queue)
        node = path[-1]
        if node == target:
            return path
        if node in visited:
            continue
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor in visited:
                continue
            new_path = list(path)
            new_path.append(neighbor)
            new_distance = distance + 1
            if heuristic_func:
                estimated_distance = heuristic_func(neighbor, target)
            else:
                estimated_distance = 0
            new_score = new_distance + estimated_distance
            heapq.heappush(queue, (new_score, new_distance, new_path))