15-451 Algorithms
Spring 2014
D. Sleator
modified: 3/17/14 GLM
Min Cost Flows March 21, 2013
----------------------------------------------------------------------------
Outline
Definition of the problem.
The no-negative-cycle property
Algorithms based on Bellman Ford
Algorithms based on Dijkstra
Avrim's notes (entitled "Network Flow II" posted earlier) outline at a
high level the key ideas for min-cost flow algorithms. These notes
will expand on those and supply more detail.
The version of the min-cost flow problem we'll discuss here is the
following. You have a graph with a source and a sink. Every edge has
a capacity, along with a non-negative cost per unit flow along that
edge. The cost of a flow is simply the sum over all edges of the
product of the flow and the cost per unit flow of the edge. Our goal
will be to compute the minimum cost flow of a given value f from s to
t. (We're going to restrict ourselves to flow graphs in which the
cost of pushing flow along an edge (u,v) is the negative of the cost
of pushing flow along the reverse edge (v,u). This property will be
preserved in all of our residual graphs. This is what will allow us
to "undo" an augmenting path, and get our "money back".)
Theorem: Suppose we have a flow F of value f in a graph G. Let G_F
denote the residual graph obtained by applying F to G. The flow F
has minimum cost if and only if G_F has no negative cycle.
Note: by a "negative cycle" we mean a sequence of edges each of which
of has non-zero residual capacity (in the direction of the cycle), and
such that the total cost around the cycle is negative.
Proof: ====> Suppose the graph has a negative cycle. We'll show that
this can be used to find a feasible flow with lower cost. At least
one unit of flow can be pushed around the cycle. This flow has a net
negative cost. The resulting flow volume from s to t is still f, but
the flow has a lower cost.
<==== If the flow does not have minimum cost then there is another
flow F' whose cost is less than that of F. Consider the flow D =
F'-F. The cost of the flow D is negative. Also note that F + D = F'.
Which means that we can augment F with D and get F'. The flow D is a
circulation, and it has negative cost. We can decompose D into a sum
of a bunch of cycles. To do this we just start following edges of D
that have positive flow until we come back to the starting point.
This must happen because flow is conserved at all verties. Now remove
that cycle from D, and continue removing cycles until D is zero.
Since the total cost of D is negative, we know that at least one of
these cycles must have had a negative value. This proves the
existance of a negative cycle in F.
QED.
Armed with this theorem it becomes trivial to construct an algorithm
for min-cost flow.
Algorithm 1 for min-cost flow of value f:
First find a flow F of value f in the graph, ignoring the costs,
using any augmenting flow algorithm. Now construct the residual
graph G_F. Now repeat the following step until the algorithm
terminates:
Search in G_F for a negative cycle. (You could use the
Bellman-Ford algorithm or the Floyd Warshall algorithm.) If G_F
has no negative cycles, then terminate. If it does have a
negative cycle, then augment F by pushing flow round that cycle
until one of the edges becomes saturated. This decreases the cost
of our flow.
Algorithm 1 is clearly correct by virtue of our theorem. It must
terminate because the cost continues to decrease by at least the
smallest nonzero number that can be formed by a linear combination of
all the cost coefficients. (Admittedly this may be small.) This does
not give a particularly satisfactory running time. We'd like to do
better.
The mistake Algorithm 1 makes is allowing for the possibilities of
negative cycles in the first place. Algorithm 2 avoids this.
Algorithm 2 for min-cost flow of value f:
Start with a zero flow F. Repeat the follwing augmenting
step until the flow value reaches f:
Find the shortest path from s to t in the residual graph G_F,
i.e. a minimum cost path from s to t.
Augment along this path as much as you can (although not
exceeding f). Update the flow F by this augmenting path.
If we've reached f, terminate.
Claim: The residual graph in Algorithm 2 never contains a negative cycle.
Proof. The initial residual graph contains no negative cycle (all
initial costs are non-negative.) So we just need to show that the
augmentation does not produce a negative cycle.
We'll do this by applying Johnson's Algorithm we saw earlier in the
course for adjusting edge lengths to make them non-negative.
On the original G_F (before augmenting) do a full single source
shortest path computation from the source s. Let d_v be the distance
computed to vertex v by this search. We know that d_v <= d_u +
cost(u,v), because if this were not so there would be a shorter path to
v via u. Now adjust the costs of all edges as follows:
cost'(u,v) = d_u - d_v + cost(u,v)
These costs are >=0. But what about the new edges that we just added
as a result of applying the augmenting path? Couldn't they create a
negative cycle? The answer is no. Here's why. The path we augment
along is a shortest path. Therefore for such edges we have:
d_u + cost(u,v) = d_v ====> cost'(u,v) = 0.
Not only that, but the adjusted cost of the reverse edge that we are
adding is also zero.
cost'(v,u) = d_u - d_v + cost(v,u) = d_u - d_v - cost(u,v) = 0
The cost around any cycle with the original costs is the same as the
cost around the cycle with the modified costs. Thus there can be no
negative cycle.
QED.
Analysis of Algorithm 2:
Each step requires doing a Bellman-Ford search, which takes time
O(nm). The number of times we have to do this is O(f). So the total
running time is O(m n f). But we can further improve this running
time.
Algorithm 3: Shortest paths with potentials
This is the same as algorithm 2, except that we keep around a set of
potentials p[] for each vertex (above referred to as d_v) such that
all edges, when adjusted by these potentials, have non-negative costs.
So the augmenting step works as follows:
Find the shortest path from s to all other vertices using Dijkstra's
algorithm. The edge lengths to use in this search are
cost'(u,v) = p[u] - p[v] + cost(u,v)
These are non-negative, and the shortest paths it finds are the same
as they would be with the unadjusted costs. Now having found all
these shortest path distances we do two things. We push flow along
the shortest path from s to t. Then we update the potentials p[] by
adding to them the shortest path distances found in this search.
Thus, all the edges, including the ones we added, remain
non-negative in length.
The algorithm is correct by virtue of the discussion of algorithm 2.
The running time is at most f repetitions of Dijkstra's algorithm.
This is O((m+n) log n) using regular heaps, and O(m + n log n) using
Fibonacci heaps. So our algorithm is: O(f (m + n log n))
Here is an implementation in C++ of Algorithm 3 by Mark Gordon (grad
student, University of Michigan). His running time is not as good as
that stated above, because his Dijkstra puts too much stuff in the
heap (log(n+m)) , and also he does not maintain adjacency lists. But
I think this is a good illustration of how you can implement these
algorithms.
/* Min Cost Flow */
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXV 810
typedef int itype;
// This implementation assumes there are not edges going in both directions
itype cap[MAXV][MAXV]; // capacity (input) this array is changed
double cost[MAXV][MAXV]; // edge cost (input) this array is changed
double pi[MAXV]; // node potential (intermediate)
double d[MAXV]; // distance (intermediate)
int p[MAXV]; // path parent (intermediate)
#define INF 1e300
#define EPS 1e-9
/* Returns the min cost for the requested flow or "-1" if the flow can't be
* made. */
double mcf(int src, int snk, int n, itype flow) {
// Create back edges
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(cap[i][j])
cost[j][i] = -cost[i][j];
memset(pi, 0, sizeof(pi));
// Main loop. Keep adding flow until we get to the desired flow or there are
// no more augmenting paths.
double cst = 0;
for(itype f = 0; f < flow; ) {
for(int i = 0; i < n; i++) d[i] = INF;
memset(p, -1, sizeof(int) * n);
d[src] = 0; p[src] = -2;
priority_queue > q;
q.push(make_pair(0.0, src));
while(!q.empty()) {
pair pr = q.top(); q.pop();
int best = pr.second;
if(fabs(pr.first + d[best]) > EPS) continue;
for(int i = 0; i < n; i++) {
if(cap[best][i] &&
d[best] + cost[best][i] + pi[best] - pi[i] + EPS < d[i]) {
d[i] = d[best] + cost[best][i] + pi[best] - pi[i];
p[i] = best;
q.push(make_pair(-d[i], i));
}
}
}
if(p[snk] == -1) return -1; // requested flow is impossible
for(int i = 0; i < n; i++) if(p[i] != -1) pi[i] += d[i];
itype aug_f = flow - f;
for(int v = snk; v != src; v = p[v]) {
aug_f = min(aug_f, cap[p[v]][v]);
}
for(int v = snk; v != src; v = p[v]) {
int u = p[v];
cap[u][v] -= aug_f;
cap[v][u] += aug_f;
cst += aug_f * cost[u][v];
}
f += aug_f;
}
return cst;
}