A*算法最短距离python代码

下面是一个使用A*算法找到两点之间最短路径的Python代码示例：

import heapq

class Node:
    def __init__(self, name):
        self.name = name
        self.neighbors = {}
        self.gCost = float('inf')  # 初始代价设为无穷大
        self.hCost = 0  # 启发式代价设为0
        self.fCost = float('inf')  # 总代价设为无穷大
        self.parent = None

    def add_neighbor(self, neighbor, distance):
        self.neighbors[neighbor] = distance

    def __lt__(self, other):
        return self.fCost < other.fCost

def distance(current, neighbor):
    # 计算两个节点之间的距离
    return current.neighbors[neighbor]

def A_star(start, goal):
    # 初始化节点和边
    nodes = {
        'A': Node('A'),
        'B': Node('B'),
        'C': Node('C'),
        'D': Node('D'),
        'E': Node('E'),
        'F': Node('F'),
        'G': Node('G')
    }

    nodes['A'].add_neighbor(nodes['B'], 2)
    nodes['A'].add_neighbor(nodes['C'], 4)
    nodes['B'].add_neighbor(nodes['C'], 1)
    nodes['B'].add_neighbor(nodes['D'], 7)
    nodes['C'].add_neighbor(nodes['E'], 3)
    nodes['D'].add_neighbor(nodes['F'], 5)
    nodes['E'].add_neighbor(nodes['F'], 2)
    nodes['F'].add_neighbor(nodes['G'], 3)

    # 初始化起始节点和终点节点
    startNode = nodes[start]
    goalNode = nodes[goal]

    # 初始化开放列表和关闭列表
    openList = []
    heapq.heapify(openList)
    heapq.heappush(openList, startNode)
    closedList = set()

    # 设置起始节点的代价为0
    startNode.gCost = 0

    while openList:
        # 从开放列表中选择具有最低总代价的节点
        currentNode = heapq.heappop(openList)

        # 如果当前节点是目标节点，则找到了最短路径
        if currentNode == goalNode:
            return reconstructPath(currentNode)

        # 将当前节点添加到关闭列表中
        closedList.add(currentNode)

        # 遍历当前节点的邻居
        for neighbor in currentNode.neighbors:
            # 如果邻居节点已在关闭列表中，则跳过
            if neighbor in closedList:
                continue

            # 计算邻居节点的代价
            neighbor.gCost = currentNode.gCost + distance(currentNode, neighbor)
            neighbor.hCost = distance(neighbor, goalNode)
            neighbor.fCost = neighbor.gCost + neighbor.hCost

            # 如果邻居节点不在开放列表中，则添加到开放列表
            if neighbor not in openList:
                heapq.heappush(openList, neighbor)
                neighbor.parent = currentNode
            # 否则，如果邻居节点已经在开放列表中，并且新代价更低，则更新代价
            elif neighbor.gCost < neighbor.parent.gCost:
                neighbor.parent = currentNode
                neighbor.gCost = neighbor.parent.gCost + distance(neighbor.parent, neighbor)
                neighbor.fCost = neighbor.gCost + neighbor.hCost

    # 如果开放列表为空且没有找到最短路径，则搜索失败
    return None

def reconstructPath(node):
    # 通过回溯节点的父节点，重构最短路径
    path = []
    current = node
    while current is not None:
        path.append(current.name)
        current = current.parent
    return list(reversed(path))

# 示例使用
start = 'A'
goal = 'G'
shortestPath = A_star(start, goal)
if shortestPath:
    print(f"The shortest path from {start} to {goal} is: {shortestPath}")
else:
    print(f"No path found from {start} to {goal}")

请注意，上述代码只是一个示例，具体的节点和边以及距离计算方式需要根据实际问题进行修改。此外，还可以根据需要添加额外的判断条件和优化措施，如检查节点的可行性、避免重复计算等。