The Rebate Edge

Shipping cost routing. Edge weights are net cost in dollars, and one carrier pays a rebate, so that leg is negative. Directed edges:

s→a 4, a→x 5, s→b 11, b→x -8, x→t 1

There is no cycle at all, so certainly no negative cycle. This is the textbook heap Dijkstra, which marks a vertex done when it is popped:

// q is a min-heap keyed on distance
while (!q.empty()) {
    auto [d_v, v] = q.top(); q.pop();
    if (done[v]) continue;
    done[v] = true;
    for (auto [to, w] : adj[v]) {
        if (dist[v] + w < dist[to]) {
            dist[to] = dist[v] + w;
            q.push({dist[to], to});
        }
    }
}

What does it leave in dist[t], and what is the true cheapest cost?

A

It never terminates, because x re-enters the heap every time b lowers it and t is relaxed again.

B

It leaves dist[t] = 10. The truth is 4, via s→b→x→t. x is popped at 9 and marked done, so the later improvement to 3 is recorded but never carried forward across x→t.

C

It leaves dist[t] = 4, which is correct. Negative edges only break Dijkstra when they form a negative cycle, and this graph has no cycles.

D

It leaves dist[t] = 10, and 10 is correct: Dijkstra's invariant guarantees the popped distance is final, so s→a→x→t is genuinely the cheapest route.