实现Dijkstra最短路径算法时遇AttributeError错误的解决咨询

错误根源 #

报错AttributeError: 'set' object has no attribute 'items'来自两个核心问题：

• 邻接表结构错误：你的graph中，某个节点的邻接关系被定义为集合（set），而非算法要求的字典（dict）。Dijkstra需要每个节点的邻接项是{邻接节点: 权重}的键值对形式，集合无法调用.items()方法。
• 未访问节点集合初始化错误：unseenNodes = graph直接绑定了原字典，后续pop操作会修改原graph，且字典的操作逻辑不适合未访问节点集合的管理。

修复步骤 #

1. 修正邻接表结构 #

确保graph的每个节点对应的值是字典，示例如下：

# 正确的邻接表结构示例
graph = {
    "Acton Town": {"Ealing Common": 2, "Chiswick Park": 3},
    "Ealing Common": {"Acton Town": 2, "Paddington": 5},
    "Paddington": {"Ealing Common": 5, "Liverpool Street": 8},
    "Liverpool Street": {"Paddington": 8, "Aldgate": 1},
    "Aldgate": {"Liverpool Street": 1}
}

禁止将邻接关系写成集合（比如"Acton Town": {"Ealing Common", "Chiswick Park"}），这种写法既没有权重信息，也不符合算法输入要求。

2. 修正未访问节点集合的初始化与操作 #

• 将unseenNodes = graph替换为创建节点集合的副本，避免修改原graph：

  unseenNodes = set(graph.keys())
  

• 集合移除节点要用remove()方法，而非字典的pop()：

  unseenNodes.remove(min_distance_node)
  

修改后的完整代码 #

def dij(graph, start, goal):
    shortest_distance = {}
    track_predecessor = {}
    # 初始化未访问节点为节点集合的副本
    unseenNodes = set(graph.keys())
    infinity = 999999
    track_path = []

    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start] = 0

    while unseenNodes:
        min_distance_node = None

        for node in unseenNodes:
            if min_distance_node is None:
                min_distance_node = node
            elif shortest_distance[node] < shortest_distance[min_distance_node]:
                min_distance_node = node

        # 此时graph[min_distance_node]是字典，可正常调用items()
        path_options = graph[min_distance_node].items()

        for (child_node, weight) in path_options:
            if weight + shortest_distance[min_distance_node] < shortest_distance[child_node]:
                shortest_distance[child_node] = weight + shortest_distance[min_distance_node]
                track_predecessor[child_node] = min_distance_node

        # 用remove移除集合中的节点
        unseenNodes.remove(min_distance_node)
    
    currentNode = goal

    while currentNode != start:
        try:
            track_path.insert(0, currentNode)
            currentNode = track_predecessor[currentNode]
        except KeyError:
            print("路径不存在")
            break

    track_path.insert(0, start)

    if shortest_distance[goal] != infinity:
        print(f"最短距离是 {shortest_distance[goal]}")
        print(f"最优路径是 {track_path}")

# 请根据实际图结构补充完整邻接表
graph = {
    "Acton Town": {"Ealing Common": 2, "Chiswick Park": 3},
    "Ealing Common": {"Acton Town": 2, "Paddington": 5},
    "Paddington": {"Ealing Common": 5, "Liverpool Street": 8},
    "Liverpool Street": {"Paddington": 8, "Aldgate": 1},
    "Aldgate": {"Liverpool Street": 1},
    "Chiswick Park": {"Acton Town": 3, "Hammersmith": 2},
    "Hammersmith": {"Chiswick Park": 2, "Paddington": 6}
}

dij(graph, "Acton Town", "Aldgate")

验证注意事项 #

运行代码前需确认：

• graph中同时包含Acton Town和Aldgate节点
• 所有节点的邻接关系均为{节点: 权重}的字典格式
• 图中存在从Acton Town到Aldgate的有效路径（否则会输出"路径不存在"）

内容的提问来源于stack exchange，提问作者mercy nwoji