A Universe of Sorts

§ Min cost flow (TODO)

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.