用代价树的广度优先搜索解决交通图问题的代码，显示最小费用路线

以下是使用代价树的广度优先搜索算法解决交通图问题，并显示最小费用路线的 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
path = []

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

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

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

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

# 输出找到目标节点的路径代价和路径
print("Path:", "->".join(path))
print("Path cost:", path_cost)

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