A*算法实现最短路径算法的python代码

以下是实现A*算法的最短路径算法的Python代码示例：

import heapq

def astar(start, goal, graph):
    """A* algorithm implementation"""

    # Initialize the open and closed lists
    open_list = []
    closed_list = set()

    # Add the start node to the open list
    heapq.heappush(open_list, (0, start))

    # Initialize the g and h scores of the start node
    g_score = {start: 0}
    h_score = {start: heuristic(start, goal)}

    while open_list:

        # Get the node with the lowest f score
        _, current_node = heapq.heappop(open_list)

        # If the current node is the goal node, we have found the shortest path
        if current_node == goal:
            return reconstruct_path(start, goal, graph)

        # Add the current node to the closed list
        closed_list.add(current_node)

        # Iterate over the neighbors of the current node
        for neighbor, distance in graph[current_node].items():

            # If the neighbor is already in the closed list, skip it
            if neighbor in closed_list:
                continue

            # Calculate the tentative g score of the neighbor
            tentative_g_score = g_score[current_node] + distance

            # If the neighbor is not in the open list, add it
            if neighbor not in [node[1] for node in open_list]:
                heapq.heappush(open_list, (tentative_g_score + heuristic(neighbor, goal), neighbor))
            # If the neighbor is already in the open list and the tentative g score is greater, skip it
            elif tentative_g_score >= g_score[neighbor]:
                continue

            # Record the new g score and h score of the neighbor
            g_score[neighbor] = tentative_g_score
            h_score[neighbor] = heuristic(neighbor, goal)

    # If there is no path from the start node to the goal node, return None
    return None

def reconstruct_path(start, goal, graph):
    """Reconstructs the shortest path from start to goal"""

    # Initialize the path with the goal node
    path = [goal]

    # Keep adding the previous node to the path until we reach the start node
    while path[-1] != start:
        current_node = path[-1]
        previous_nodes = graph[current_node]
        previous_node = min(previous_nodes, key=lambda node: previous_nodes[node])
        path.append(previous_node)

    # Reverse the path and return it
    return list(reversed(path))

def heuristic(node, goal):
    """Returns the estimated distance between node and goal"""

    # Use the Manhattan distance as the heuristic
    return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

# Example usage:
graph = {
    (0, 0): {(1, 0): 1, (0, 1): 1},
    (1, 0): {(0, 0): 1, (1, 1): 1},
    (0, 1): {(0, 0): 1, (1, 1): 1},
    (1, 1): {(1, 0): 1, (0, 1): 1, (2, 1): 1},
    (2, 1): {(1, 1): 1, (2, 2): 1},
    (2, 2): {(2, 1): 1}
}

start = (0, 0)
goal = (2, 2)

print(astar(start, goal, graph)) # Output: [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2)]

该示例代码实现了A*算法，使用了堆（heapq）来优化寻找最小f值的节点。在计算路径时，使用了启发式函数（heuristic），这里使用的是曼哈顿距离（Manhattan distance）。该代码可以寻找从一个起始点到一个目标点的最短路径。