- Problem statement: Find a maximal flow with minimum cost.

- Find max flow.
- Find negative cost cycle in residual graph of max flow. Push flow around the negative cost cycle.

- 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.

- 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 ].

- 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.

- 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.

- 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.