Why does this not work:
while (!pq.empty()) {
int curr=pq.top().second; int l=pq.top().first;
pq.pop();
if (curr==n-1) break;
for (auto a: adj[curr]) {
if (dist[a.second]>l+a.first) {
parent[a.second]=curr;
dist[a.second]=l+a.first;
pq.push({dist[a.second], a.second});
}
}
}
and this does:
while (!pq.empty()) {
int curr=pq.top().second; int l=pq.top().first;
pq.pop();
if (visited[curr]) continue;
visited[curr]=1;
for (auto a: adj[curr]) {
if (dist[a.second]>l+a.first) {
parent[a.second]=curr;
dist[a.second]=l+a.first;
pq.push({dist[a.second], a.second});
}
}
}
Shouldn't the visited array not be necessary (since we only visit each node once, the first time, where the distance is the shortest, so each successive time, if (dist[a.second]>l+a.first) does not hold and it's not added again to the queue?
question from:
https://stackoverflow.com/questions/65911039/visited-array-in-dijkstras 与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…