At any moment the deque holds at most two distinct distances, d and d + 1, with all the d entries in front, so taking from the front returns the smallest tentative distance - which is the only thing the heap was ever doing, now at O(1). A 0 edge reaches its target at the same distance as the vertex just popped, so it belongs at the front. A 1 edge reaches d + 1 and belongs at the back, and either way the two-value invariant holds. A vertex can be pushed several times before it is popped, so the dist[u] + w < dist[v] test is what keeps the stale copies harmless. The idea generalises to weights 0..k as k + 1 buckets walked in order, which is Dial's algorithm.