## § Min cost flow (TODO)

• Problem statement: Find a maximal flow with minimum cost.
1. Find max flow.
2. Find negative cost cycle in residual graph of max flow. Push flow around the negative cost cycle.

#### § Relation between max flow and min cost circulation

• Recall that min cost circulation asks to compute a circulation with minimum cost [no maximality constraint ].
• Given a flow network $(V, E, s, t, C)$ ( $C$ is capacity fn), create a new cost function $c: V \to \mathbb R$ which assigns cost zero to all edges in the flow networ. Also add a new edge $t \to s$ which has infinite capacity, cost $-1$.
• A circulation with cost lower than zero will have to use the $t \to s$ edge. To get minimum cost, it must send as much flow through this edge as possible. For it to be a circulation, the full flow in the network must be zero. So suppose we send $f$ units of flow back from $t$ to $s$. Then we must send $f$ units of flow from $s$ to $t$ for it to be a circulation. Incrasing $f$ (max flow) decreases the cost of the circluation! Thus, max flow is reduced to min cost circulation.

#### § Min Cost Flow in general

• First find max flow using whatever.
• Next, we need to find negative cost cycle in the residual graph.
• Use bellman ford, or SPFA to find negative cost cycles in $O(VE)$ time [run edge relaxation $|V|$ times ].

#### § Minimum mean cycle

• Which is best cycle to push flow around to reduce cost? The min cost cycle may not be best, since it may have very little capacity.
• A negative cycle with max capacity may not have good cost.
• Correct: total cost/number of edges --- that is, the mean cost.

#### § shortest path as circulation.

• Need to find single source shortest path in a graph (with possibly negative edges, no negative cycles).
• We have a balance at each vertex $v$, which tells us how much extra flow must can have coming in versus going out. So, $\sum_u f(l \to v) - \sum_w f(v \to r) = b(v)$. Intuitively, the balance is stored in a tank at the vertex.
• We need total balance to be zero.
• We set the source $s$ to have balance $1-v$ (supply) and all the other nodes to have balance $1$ (demand).
• Let the cost of each edge be the distance, let the capacity of each edge be infinite.
• Now, what is a min cost flow which obeys the demands?
• Consider the shortest path tree. Imagine it as carrying a flow. Then the shortest path tree indeed obeys the flow constraints.
• To convert this into circulation, add back edges from each node back to the source, with a capacity of 1, cost of zero.
• This converts shortest path trees into flows/circulations.

#### § Min cost circulation algorithms

• Old algorithm: start with a circulation that obeys balance, then push more around (by using negative cycles)
• New algorithm (successive shortest path): remove all negative cycles, then restore balance constraints.
• how to remove negative cycles? We can just send flow down all negative edges. The resdiual graph will contain no negative cycles. (NOTE: we don't have a valid flow at this point!) This leaves us with resdiual balances at each vertex, about how much more flow we need to send.