使用优先级队列的 Dijkstra 算法中是否真的需要访问的数组？

Question

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;
}

我使用优先级队列为Dijkstra的算法编写代码，但忘记初始化访问的数组以跟踪访问的顶点。我提交了代码，所有的测试用例都通过了。是真的需要被访问的数组，还是我遗漏了什么？

Answer 1

由于算法跟踪到节点的(到目前为止(最短距离，if (dfn+dis < distance[currNode])语句将阻止算法重新访问它已经访问过的节点，因为它为重新访问节点而进行的循环将添加到该重新访问节点的已有距离上，因此此条件为假(假设权重为正(。

因此，实际上，在Dijkstra算法的这个变体中，您不需要访问数组。还可以看看维基百科提供的伪代码中没有它。

Answer 2

这并不是Dijkstra的算法，因为Dijkstra的算法涉及每个节点最多从优先级队列中添加和删除一次。当具有负权重边时，此版本将在队列中重新插入节点。如果你有负权重循环，它也会进入一个无限循环。

请注意，维基百科版本使用decrease key操作，它不会插入到if语句中的优先级队列中。

我不知道你指的是哪个版本使用了visited数组，但visited数组很可能达到了同样的目的。

这更接近于Bellman-Ford算法，它也可以用队列来实现(在实践中，如果你这样做，通常比像大多数源中所示的那样通过迭代边|V|次更快(。优先级队列可以获得相同的结果，但它将比简单的FIFO队列慢。对于你提交给的在线法官来说，这可能已经足够快了。

一句话：你所拥有的不是Dijkstra的算法。访问的数组可能是Dijkstra的必需数组。你应该编辑你的帖子来显示那个版本，这样我们就可以肯定了。