Python实现带权图BFS最短路径适配带权邻接表报错如何解决

• 原有BFS代码默认适配无权图结构，邻接表中存储的直接是字符串类型的节点名
• 你修改后的带权邻接表每个邻接项是[相邻节点名, 边权重]的列表，原有代码直接把这个列表加入了路径队列，下一轮遍历取path[-1]作为节点查询字典时，列表属于不可哈希类型，无法作为字典的key，因此抛出该报错。

你只需要在遍历邻接项时拆分出节点名和边权重，将节点名加入路径队列即可，如果需要同步计算总通行距离，可以将队列改为存储「当前路径、总权重」的二元组，修改后的完整代码如下：

def BFS_SP(graph, start, goal):
    explored = []
    # 队列存储结构调整为 (当前路径列表, 路径累计总权重)
    queue = [([start], 0)]
    
    if start == goal:
        print("Same Node")
        return
    
    while queue:
        path, total_weight = queue.pop(0)
        node = path[-1]
        
        if node not in explored:
            neighbours = graph[node]
            for neighbour_item in neighbours:
                # 拆分邻接项的节点名和边权重
                neighbor_name, edge_weight = neighbour_item
                new_path = list(path)
                new_path.append(neighbor_name)
                new_total = total_weight + edge_weight
                queue.append((new_path, new_total))
                
                if neighbor_name == goal:
                    print("最短路径 = ", *new_path)
                    print("路径总通行距离 = ", new_total)
                    return
            explored.append(node)

    print("So sorry, but a connecting path doesn't exist :(")
    return

# 驱动代码直接使用你提供的带权邻接表即可
if __name__ == "__main__":
    graph = {
        'Arad':             [['Zerind', 75], ['Timisoara', 118], ['Sibiu', 140]],
        'Bucharest':        [['Urziceni', 85], ['Giurgiu', 90], ['Pitesti', 101], ['Fagaras', 211]],
        'Craiova':          [['Dobreta', 120], ['Pitesti', 138], ['Rimnicu Vilcea', 146]],
        'Dobreta':          [['Mehadia', 75], ['Craiova', 120]],
        'Eforie':           [['Hirsova', 86]],
        'Fagaras':          [['Sibiu', 99], ['Bucharest', 211]],
        'Giurgiu':          [['Bucharest', 90]],
        'Hirsova':          [['Eforie', 86], ['Urziceni', 98]],
        'Iasi':             [['Neamt', 87], ['Vaslui', 92]],
        'Lugoj':            [['Mehadia', 70], ['Timisoara', 111]],
        'Mehadia':          [['Lugoj', 70], ['Dobreta', 75]],
        'Neamt':            [['Iasi', 87]],
        'Oradea':           [['Zerind', 71], ['Sibiu', 151]],
        'Pitesti':          [['Rimnicu Vilcea', 97], ['Bucharest', 101], ['Craiova', 138]],
        'Rimnicu Vilcea':   [['Sibiu', 80], ['Pitesti', 97], ['Craiova', 146]],
        'Sibiu':            [['Rimnicu Vilcea', 80], ['Fagaras', 99], ['Arad', 140], ['Oradea', 151]],
        'Timisoara':        [['Lugoj', 111], ['Arad', 118]],
        'Urziceni':         [['Bucharest', 85], ['Hirsova', 98]],
        'Vaslui':           [['Iasi', 92], ['Urziceni', 142]],
        'Zerind':           [['Oradea', 71], ['Arad', 75]]
    }
    BFS_SP(graph, 'Arad', 'Bucharest')

上面的修改仅解决了代码运行报错的问题，标准BFS逻辑是按边数优先级遍历，只能找到边数最少的路径，无法得到边权总和最小的最短路径，如果你的核心需求是计算带权图的最短路径，可按以下顺序学习相关算法：

• 无负权边的带权图最短路径：Dijkstra算法
• 存在负权边的带权图最短路径：Bellman-Ford算法
• 需要结合启发信息优化搜索效率：A*算法

内容的提问来源于stack exchange，提问作者Meike Magdalena Büttner