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?
Sign in to answer questions and track your progress
Sign In