基于priority queue实现dijkstra algorithm为何无需检查visited node

你提到的核心代码片段如下：

while (!pq.empty())
{
    
    int u = pq.top().second;
    pq.pop();
 
    // Get all adjacent of u.
    for (auto x : adj[u])
    {
        int v = x.first;
        int weight = x.second;
 
        if (dist[v] > dist[u] + weight)
        {
            dist[v] = dist[u] + weight;
            pq.push(make_pair(dist[v], v));
        }
    }
}

很多人初学Dijkstra时会记住“需要visited数组标记已确定最短距离的节点”的写法，看到这段没有访问状态检查的代码会怀疑有逻辑漏洞，实际上这段实现是完全正确的，不需要额外加visited检查，原因如下：

• 小顶堆的性质保证节点首次出堆即拿到最短距离：代码中使用的是存储<路径长度, 节点>对的小顶优先队列，永远会把当前已知路径最短的节点先弹出堆。对任意节点来说，第一次从堆顶被弹出时，dist数组中存储的该节点距离就是源点到它的全局最短路径长度——如果还存在更短的到达路径，对应更短距离的堆条目一定会更早排到堆顶被弹出，根本不会让长距离的条目先出堆。
• 优先队列本身不支持删除内部旧条目，必然存在同一节点的多份记录：每次松弛操作找到到节点v的更短路径时，我们都是直接把新的<更短距离, v>推入堆，不会特意删除堆里之前存的、对应更长距离的v的旧条目（普通二叉堆也不支持高效的随机删除操作），所以堆里可能同时存在同一个节点的多份不同距离的记录。
• 松弛判断天然过滤所有无效的旧节点记录：等堆里存的旧条目（对应更长距离、已经处理过的节点）后续被弹出时，根本不会触发错误更新。因为此时dist数组里存的该节点的距离已经是更小的最短值，用旧条目的长距离计算邻接点的路径长度时，得到的结果必然大于等于之前用最短距离松弛后的邻接点距离，dist[v] > dist[u] + weight的判断条件永远不成立，遍历邻接点的操作不会产生任何有效修改，等于自动跳过了这些无效的旧记录。

实际上显式加visited数组的写法只是一个微小的性能优化：在节点第一次出堆时标记为已访问，后续再弹出同一节点的旧条目时直接跳过遍历邻接点的步骤，省几次无意义的判断。但不加visited检查完全不影响算法正确性，靠松弛逻辑本身就完成了无效记录的过滤，不需要额外维护访问状态。

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