为何Dijkstra算法需更新已探索节点成本？求示例说明

首先纠正一个关键误区：当节点被从优先队列（最小堆）中取出并标记为“已探索”时，它的最短路径已经确定，后续不可能出现更短路径——这是Dijkstra算法的核心保证，因为所有边权重非负，任何后续路径的长度只会更长。

但你看到的“重新加入frontier并更新成本”的场景，通常是因为实现中没有严格区分「已加入frontier」和「已完成探索（弹出队列）」这两种状态。如果你的实现是只要节点被加入frontier就标记为“已探索”并拒绝后续处理，就会出现错误，以下是必须更新路径的典型示例：

示例场景 #

假设我们有一个无向图，节点和边权重如下：

• A → B，权重5
• A → C，权重2
• C → B，权重2

错误实现的执行流程（你的当前逻辑） #

1. 初始状态：起点A的路径成本为0，加入frontier；已探索列表为空。
2. 取出A，标记为已探索，处理邻居：
   • B的路径成本为0+5=5，加入frontier，标记为已探索。
   • C的路径成本为0+2=2，加入frontier，标记为已探索。
3. 取出C（成本2），处理邻居B时，发现B已在已探索列表中，直接跳过。
4. 最终得到B的路径成本为5，但实际最短路径是A→C→B，总成本4。

正确实现的执行流程 #

1. 初始状态：起点A的路径成本为0，加入frontier；已探索列表为空，维护一个记录每个节点当前最短路径的字典。
2. 取出A，标记为已探索，处理邻居：
   • B的路径成本5，记录到字典，加入frontier。
   • C的路径成本2，记录到字典，加入frontier。
3. 取出C（成本2），标记为已探索，处理邻居B：
   • 计算新路径成本2+2=4，比字典中B的当前成本5更小。
   • 更新字典中B的成本为4，将B重新加入frontier（或更新frontier中B的条目）。
4. 取出B（成本4），标记为已探索，处理其邻居（无未探索节点）。
5. 最终得到B的正确最短路径成本4。

核心原因 #

你的实现错误地将「加入frontier」等同于「已完成探索」，但实际上，节点加入frontier只是表示我们发现了一条到达它的路径，但这条路径不一定是最短的。只有当节点被从优先队列中取出时，我们才能确定当前路径是最短的——因为优先队列总是弹出当前成本最小的节点，而所有边权重非负，后续不可能出现更短的路径。

允许节点重新加入frontier的实现方式，本质是用“冗余入队”替代复杂的堆元素更新操作，这样实现更简单，且不会影响算法正确性（后续取出旧的、更长路径的节点时，直接跳过即可）。

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