Python实现Dijkstra算法更换自定义图后触发KeyError报错如何解决

问题原因 #

这个报错是参考代码本身存在逻辑缺陷，你定义的图结构没有错误。

缺陷根源 #

Dijkstra算法的核心性质是：当某个节点被从优先队列中弹出时，就已经找到了从起点到该节点的最短路径，后续不需要再对该节点做任何更新操作。
你用的参考代码在弹出节点u时，直接将u从entry_finder字典中删除了，但是后续遍历其他节点的邻接边时，如果遇到已经被弹出、不在entry_finder中的节点，直接访问entry_finder[v]就会抛出KeyError。
之前的课堂示例可以正常运行，只是刚好示例图的结构不会触发「已处理节点作为其他节点邻接边目标」的场景，不代表代码没有问题。

修复方案 #

只需要在处理邻接边的逻辑前，加一层判断：如果邻接节点v已经不在entry_finder中，说明已经确定最短路径，直接跳过即可。
修改后的dijkstra函数循环部分代码如下：

while pq:
    d_u, u = pop_entry()
    if u is not None and u != REMOVED:
        costs[u] = d_u
        for e in G[u]:
            v, w = e
            # 新增判断：v已经被处理过就跳过
            if v not in entry_finder:
                continue
            entry_v = entry_finder[v]
            d_v = entry_v[0]
            if d_v > d_u + w:
                add_entry(v, d_u + w)
                pred[v] = u

修改后运行你定义的图，就能正常输出最短路径开销和前驱节点结果，不会再抛出KeyError。

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