Leave The Stale Ones In

Dijkstra with a binary heap, written the way it is written when the heap has no decrease-key:

priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
d[s] = 0; pq.push({0, s});
while (!pq.empty()) {
    auto [dv, v] = pq.top(); pq.pop();
    if (dv != d[v]) continue;                       // line 5
    for (auto [u, w] : adj[v])
        if (d[v] + w < d[u]) { d[u] = d[v] + w; pq.push({d[u], u}); }
}

A vertex can sit in the heap several times at several distances, because nothing is ever removed when a shorter path is found. Delete line 5. What is now true?

Nothing changes at all. Line 5 is a micro-optimization, and any entry it would skip is popped after the vertex is already finalized, so the loop body is a no-op anyway.

The distances are still correct. The relaxation reads d[v], not the stale dv, so a repeat visit can only re-scan edges that no longer improve anything. The cost is extra adjacency scans on top of the same $O(m \log m)$ heap work.

Distances can come out too large, because a stale entry re-relaxes v's neighbours from an outdated longer distance and overwrites the shorter values already stored.

The loop can run forever, since every re-visit of v pushes its neighbours again and the heap never drains.