使用优先队列实现Dijkstra算法时，visited数组是否必需？

云原生阿岚

2026-8-20

Dijkstra算法中visited数组真的必要吗？

我写基于优先队列的Dijkstra算法时，忘了初始化用于追踪已访问顶点的visited数组，但提交后所有测试用例都通过了。想请教下：visited数组是不是真的有必要？还是我忽略了某些关键点？

我的代码如下：

vector<int> dijkstra(vector<vector<int>> &vec, int vertices, int edges, int source) 
{
    vector <pair<int,int>> adj[vertices];
    for (int i=0;i<edges;i++)
    {
        int u = vec[i][0];
        int v = vec[i][1];
        int w = vec[i][2];
        
        adj[u].push_back(make_pair(v,w));
        adj[v].push_back(make_pair(u,w));
    }
    
    vector<int> distance(vertices,INT_MAX);
    distance[source]= 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    pq.push(make_pair(0,source));
    
    while(!pq.empty())
    {
        int dis = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        for (auto adjacentNode : adj[node])
        {
            int currNode = adjacentNode.first;
            int dfn = adjacentNode.second;
            
            if (dfn+dis < distance[currNode])
            {
                distance[currNode]= dfn+dis;
                pq.push(make_pair(distance[currNode], currNode));
            }
        }
    }

    return distance;
}

结论：visited数组并非必须，但影响性能

你的代码能通过所有测试用例完全合理，核心原因在于Dijkstra算法的本质逻辑，以及非负权边的前提：

为什么没visited数组也能得到正确结果？
Dijkstra算法依赖「非负边权」的前提，当你从优先队列中取出一个节点时，这个节点的当前dis值必然是它的最短路径长度——因为所有边权非负，不可能再通过其他路径得到更短的距离。
即使队列中存在同一个节点的旧条目（比如之前以更大的距离入队），当后续取出这些旧条目时，dis会大于已经记录的distance[node]，这时候代码里的松弛判断dfn+dis < distance[currNode]会自动不成立，不会更新任何值，也不会产生无效的入队操作。所以最终distance数组的结果依然是正确的。
visited数组的真实作用是什么？
它是性能优化手段，用来剪枝：当标记一个节点为已访问后，后续再从队列中取出该节点的旧条目时，可以直接跳过邻接节点的遍历操作，避免重复计算，减少优先队列的操作次数。
没有visited数组的话，队列里会堆积大量同一个节点的旧条目，每次pop和遍历都会浪费时间，但不会影响结果正确性——测试用例规模不大时，这种性能差异可能体现不出来。

更优的替代方案
不用visited数组，也能实现类似的剪枝效果：在取出节点后加一个判断，如果当前dis大于distance[node]，直接跳过该节点的处理。这种方式比visited数组更灵活，能自动过滤所有无效的旧条目，代码修改如下：

while(!pq.empty())
{
    int dis = pq.top().first;
    int node = pq.top().second;
    pq.pop();
    
    if (dis > distance[node]) continue; // 替代visited数组的剪枝逻辑
    
    for (auto adjacentNode : adj[node])
    {
        int currNode = adjacentNode.first;
        int dfn = adjacentNode.second;
        
        if (dfn+dis < distance[currNode])
        {
            distance[currNode]= dfn+dis;
            pq.push(make_pair(distance[currNode], currNode));
        }
    }
}

注意前提
以上所有结论都建立在图中所有边权非负的基础上。如果存在负权边，不管有没有visited数组，Dijkstra算法都无法保证正确性，此时应该使用Bellman-Ford或SPFA算法。

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

使用优先队列实现Dijkstra算法时，visited数组是否必需？

结论：visited数组并非必须，但影响性能 #

结论：visited数组并非必须，但影响性能