Definition

  • A price function p : V → ℝ induces a reduced cost on edge uv 1:11:24, 1:12:16:

    c_p(uv) = c(uv) + p(u) − p(v)

  • Intuition — the gold trader: you buy gold at u (pay p(u)), ship it (pay c(uv)), and sell it at v (earn p(v), i.e. negative cost) 1:12:16, 1:13:10.

The characterization

f is an optimal min-cost circulation iff there exists a price function p on the residual graph G_f such that all reduced costs are non-negative 1:13:23.

The pivotal invariant

  • Cycle costs are identical under c and c_p — the p(u) and p(v) terms telescope and cancel around any cycle 1:14:08.

Proof, direction 1 (p exists ⟹ optimal)

  • All reduced costs non-negative ⇒ every cycle's reduced cost is non-negative ⇒ (by cancellation) every cycle's real cost is non-negative ⇒ no negative cycles ⇒ optimal, by the previous section 1:14:08, 1:14:53.

Proof, direction 2 (optimal ⟹ p exists) — the construction

Given that G_f has no negative cycles 1:14:53, 1:15:29, 1:16:03:

  1. Introduce a new vertex s with zero-cost edges to every vertex.
  2. Set p(u) = shortest-path distance from s to u under the costs — well defined precisely because there are no negative cycles.
  3. Non-negativity of all reduced costs is then exactly the triangle inequality. Left to the reader to verify offline.