15-451 Algorithms Spring 2013 D. Sleator 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 minimal 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 minimal 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. 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 the Johnson/Karp trick 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; }