用代价树的广度优先搜索解决交通图问题的代码

以下是使用代价树的广度优先搜索算法解决交通图问题的 Python 代码示例：

# 定义一个交通图，使用邻接表表示，每个节点包含相邻节点和边的代价
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'D': 5, 'E': 4},
    'C': {'F': 6},
    'D': {'G': 7},
    'E': {'G': 4},
    'F': {'G': 3},
    'G': {}
}

# 定义起始节点和目标节点
start_node = 'A'
goal_node = 'G'

# 定义一个队列和一个哈希表，用于存储待扩展的节点和已访问的节点
queue = [(start_node, 0)]
visited = {start_node: 0}

# 定义一个变量，用于记录找到目标节点的路径代价
path_cost = 0

# 进行广度优先搜索
while queue:
    # 取出队列中的第一个节点，并计算其代价
    node, cost = queue.pop(0)

    # 如果当前节点是目标节点，记录路径代价并退出循环
    if node == goal_node:
        path_cost = cost
        break

    # 遍历当前节点的相邻节点
    for neighbor, neighbor_cost in graph[node].items():
        # 计算相邻节点的路径代价
        total_cost = cost + neighbor_cost

        # 如果相邻节点还没有被访问，或者当前路径代价更小，则添加到队列中
        if neighbor not in visited or total_cost < visited[neighbor]:
            visited[neighbor] = total_cost
            queue.append((neighbor, total_cost))

# 输出找到目标节点的路径代价
print(path_cost)

在上面的代码中，我们使用邻接表表示交通图，并使用一个队列和一个哈希表来存储待扩展的节点和已访问的节点。在进行广度优先搜索时，我们首先从队列中取出第一个节点，并计算其代价。接着，我们遍历当前节点的相邻节点，并计算相邻节点的路径代价。如果相邻节点还没有被访问，或者当前路径代价更小，则将其添加到队列中。如果找到目标节点，则记录路径代价并退出循环。最后，输出找到目标节点的路径代价。