Maximum flow by Edmonds-Karp for O (NM 2 )
Warning: This article is outdated and contains errors and is not recommended for reading. After some time, the article will be completely rewritten.
Suppose we are given a graph G, which highlights two peaks: the source S and drain T, and each rib is defined bandwidth C u, v . The flow F may be represented as a stream of a
substance which could pass through the network from source to drain, if we consider the graph as a network of tubes with some bandwidth. Ie stream - the function F u, v , defined on the set of edges of the graph.
The challenge is to find the maximum flow. Here we consider the method of Edmonds-Karp, who works for the O (NM 2 ), or (another estimate) O (FM), where F - value of the desired flow. The algorithm was proposed in 1972.
Algorithm
Residual bandwidth is called bandwidth rib net current flow along this edge. It must be remembered that if a stream flows through the oriented edge, there is a so-called reverse edge (directed in the opposite direction), which will have zero capacity, and which will take place the same value on stream, but with a minus sign. If the edge has been oriented, it breaks up into two equally oriented edge bandwidth, and each of these edges is reversed for the other (if one proceeds flow F, then proceeds differently -F).
The general scheme of the algorithm Edmonds-Karp is. First, assume the flow to zero. Then look for complementary way, ie simple path from S to T at the edges whose residual capacity is strictly positive. If supplementing the path was found, then produced an increase in current flow along this path. If the same path is not found, the current flow is maximized. To find complementary ways can be used as a bypass to the width and depth of a bypass .
Consider a more accurate procedure to increase the flow. Suppose we found some complementary way, then let C - the smallest of the residual capacity of edges of this path. Procedure to increase the flow is as follows: for each edge (u, v) fulfill complementary ways: F u, v = + C, and F v, u = - F u, v (or, equivalently, F v, u - = C).
The quantity of flow is the sum of all non-negative values of F S, v , where v - any vertex joined to the source.
Implementation
const int inf = 1000 * 1000 * 1000;
typedef vector <int> graf_line;
typedef vector <graf_line> graf;
typedef vector <int> vint;
typedef vector <vint> vvint;
int main () {
int n;
cin >> n;
vvint c (n, vint (n));
for (int i = 0; i <n; i ++)
for (int j = 0; j <n; j ++) cin >> c [i] [j];
// Source - vertex 0, the stock - the top n-1 vvint f (n, vint (n));
for (;;) {
vint from (n, -1);
vint q (n);
int h = 0, t = 0;
q [t ++] = 0;
from [0] = 0;
for (int cur; h <t;) {
cur = q [h ++];
for (int v = 0; v <n; v ++) if (from [v] == -1 &&
c [cur] [v] -f [cur] [v]> 0) {
q [t ++] = v;
from [v] = cur;
} }
if (from [n-1] == 1) break;
int cf = inf;
for (int cur = n-1; cur! = 0;) {
int prev = from [cur];
cf = min (cf, c [prev] [cur] -f [prev] [cur]);
cur = prev;
}
for (int cur = n-1; cur! = 0;) { int prev = from [cur];
f [prev] [cur] + = cf;
f [cur] [prev] - = cf;
cur = prev;
} }
int flow = 0;
for (int i = 0; i <n; i ++) if (c [0] [i])
flow + = f [0] [i];
cout << flow;
}
Maximum flow by pushing predpotoka for O (N 4 )
Suppose we are given a graph G, which highlights two peaks: the source S and drain T, and each rib is defined bandwidth C u, v . The flow F may be represented as a stream of a
substance which could pass through the network from source to drain, if we consider the graph as a network of tubes with some bandwidth. Ie stream - the function F u, v , defined on the set of edges of the graph.
The challenge is to find the maximum flow. Here we consider a method of pushing predpotoka working for O (N 4 ), or, more precisely, for the O (N 2 M). The algorithm was proposed by Goldberg in 1985.
Algorithm
The general scheme is the algorithm. At each step, we will consider some predpotok - ie feature that allows flow properties similar, but not necessarily satisfy the law of conservation of flow. At each step, we try to apply any of the two operations: pushing or lifting the top of the stream. If at some stage it will become impossible to apply any of the two operations, we have found that the desired flow.
For each vertex defined its height H u , H And S = N, H T = 0, and for any residual edges (u, v), we have H u <= H v + 1.
For each node (except S) it is possible to determine the excess: E u = F V, u . Top with positive excess is called overflow.
Operation push Push (u, v) is available when the vertex u is full, the residual capacity of the Cf u, v > 0 and H u H = v + 1. Operation push is to maximize the flow from u to v, limited excess E u and residual capacity Cf u, v .
Operation lift Lift (u) raises crowded vertex u to the maximum height. Ie H u = 1 H + min { v }, where (u, v) - residual rib.
It remains only to consider the initialization flow. Only necessary to initialize the following values: F S, v C = S, v , F u, S = - C u, S , the remaining values are set equal to zero.
Implementation
const int inf = 1000*1000*1000;
typedef vector<int> graf_line;
typedef vector<graf_line> graf;
typedef vector<int> vint;
typedef vector<vint> vvint;
void push (int u, int v, vvint & f, vint & e, const vvint & c) {
int d = min (e[u], c[u][v] - f[u][v]);
f[u][v] += d;
f[v][u] = - f[u][v];
e[u] -= d;
e[v] += d;
}
void lift (int u, vint & h, const vvint & f, const vvint & c) {
int d = inf;
for (int i = 0; i < (int)f.size(); i++) if (c[u][i]-f[u][i] > 0)
d = min (d, h[i]);
if (d == inf) return;
h[u] = d + 1;
}
int main()
{ int n;
cin >> n;
vvint c (n, vint(n));
for (int i=0; i<n; i++)
for (int j=0; j<n; j++) cin >> c[i][j];
// исток - вершина 0, сток - вершина n-1 vvint f (n, vint(n));
for (int i=1; i<n; i++) {
f[0][i] = c[0][i];
f[i][0] = -c[0][i];
}
vint h (n);
h[0] = n;
vint e (n);
for (int i=1; i<n; i++) e[i] = f[0][i];
for ( ; ; ) {
int i;
for (i=1; i<n-1; i++) if (e[i] > 0)
break;
if (i == n-1) break;
int j;
for (j=0; j<n; j++)
if (c[i][j]-f[i][j] > 0 && h[i]==h[j]+1) break;
if (j < n)
push (i, j, f, e, c);
else lift (i, h, f, c);
}
int flow = 0;
for (int i=0; i<n; i++) if (c[0][i])
flow += f[0][i];
cout << max(flow,0);
}
Modification of the method of pushing
predpotoka for finding the maximum flow of O (N 3 )
It is assumed that you have already read predpotoka push method for finding the maximum flow of O (N 4 ) .
Description
Modification is very simple: at each iteration among all crowded vertices we select only those vertices that have the Greatest height , and use push / lift only to those
heights. Furthermore, to select a maximum height of vertices we do not need any data structure, simply store a list of nodes with the greatest height and recalculate it only when all the vertices in the list have been processed (then be added to list is already at the top with height), and when a new vertex crowded with greater height than the list, clear the list and add the top of the list.
Despite its simplicity, this modification reduces the asymptotic behavior of the whole
procedure. To be exact, asymptotic received algorithm is O (NM + N 2 sqrt (M)) , in the worst case is O (N 3 ) .
This modification was proposed Cheriyanom (Cheriyan) and Maheshwari (Maheshvari) in 1989
Implementation
Here is a ready implementation of this algorithm.
Unlike conventional algorithm push - only in the presence of an array maxh, which will be kept rooms crowded peaks with a maximum height. The size of the array is specified in the variable sz. If at some iteration is that the array is empty (sz == 0), then we fill it (just passing through all vertices); if it is then the array is still empty, the crowded peaks not, and the algorithm stops. Otherwise, we go over the tops of the list, applying to them pushing or lifting. After the operation of pushing the current vertex may cease to be crowded, in this case, remove it from the list maxh. If, after some operations of raising the height of the current node becomes greater than the height of vertices in the list maxh, then we clear the list (sz = 0), and immediately proceed to the next iteration of the algorithm push (which will be built a new list maxh).
const int INF = 1000 * 1000 * 1000;
int main () { int n;
vector <vector <int>> c (n, vector <int> (n));
int s, t;
Reading ... n, c, s, t ...
vector <int> e (n);
vector <int> h (n);
h [s] = n-1;
vector <vector <int>> f (n, vector <int> (n));
for (int i = 0; i <n; ++ i) { f [s] [i] = c [s] [i];
f [i] [s] = -f [s] [i];
e [i] = c [s] [i];
}
vector <int> maxh (n);
int sz = 0;
for (;;) {
if (! sz)
for (int i = 0; i <n; ++ i)
if (i! = s && i! = t && e [i]> 0) { if (sz && h [i]> h [maxh [0]])
sz = 0;
if (! sz || h [i] == h [maxh [0]])
maxh [sz ++] = i;
} if (! sz) break;
while (sz) {
int i = maxh [sz-1];
bool pushed = false;
for (int j = 0; j <n && e [i]; ++ j)
if (c [i] [j] -f [i] [j]> 0 && h [i] ==
h [j] +1) {
pushed = true;
int addf = min (c [i] [j] -f [i]
[j], e [i]);
f [i] [j] + = addf, f [j] [i] - = addf;
e [i] - = addf, e [j] + = addf;
if (e [i] == 0) --sz;
if (! pushed) {} h [i] = INF;
for (int j = 0; j <n; ++ j)
if (c [i] [j] -f [i] [j]> 0 && h [j] +1 <h [i])
h [i] = h [j] +1;
if (h [i]> h [maxh [0]]) { sz = 0;
break;
} }
} }
... Output stream f ...
}
Finding the flow in the graph in which each rib specified minimum and maximum flow
Suppose we are given a graph G, where for each edge in addition to the capacity (maximum flow along this edge) is specified and the minimum value of the flow, which should take place on the edge.
Here we consider two problems: 1) the need to find an arbitrary stream that satisfies all the constraints, and 2) you want to find the minimum flow that satisfies all the constraints.
Solution of Problem 1
Denote by L i minimum value stream which may pass through the i-th rib, and by R i - its maximum value.
Proizvedёm in the following graph changes . Add a new source S 'and runoff T'. Consider all edges that have L i is different from zero. Let i - number of such edges. Let the ends of the rib (oriented) - this is the top of the A i and B i . Add Edge (S ', B i ), in which L = 0, L = R i , add an edge (A i , T '), in which L = 0, L = R i , and at the very edges of the i-th set R i = R i - L i , L and i = 0. Finally, add a graph edge from T to S (old drain and source) in which L = 0, R
= INF.
After performing these transformations all edges of the graph will have L i = 0; we have reduced this problem to the usual problem of finding the maximum flow (but in a modified box with the new source and drain) (in order to understand why the maximum - read the following explanation).
The correctness of these transformations more difficult to
understand. Informal explanation is. Each edge which L i is different from zero, we replace the two edges, one with a capacity of L i , and the other - with R i -L i . We need to find a thread that would necessarily saturated the first edge of the pair (ie, flow along this edge should be equal to L i ); second edge we care less - flow along it can be anything, as long as it does not exceed its capacity. So, we need to find a thread that would definitely satiated some set of edges. Let us consider each such edge, and perform such an operation: to sum to the end edge of a new source S ', to sum edge from its beginning to the drain of T', itself an edge to delete, and runoff from the old to the old source of the T S will hold an edge infinite bandwidth. By these actions, we proimitiruem that this edge is saturated - the rib will flow L i flow units (we simulate it with a new source, which feeds on the right end of the rib flow amount), and will flow into it again L iflow units (but instead of ribs this thread gets a new sink). Flow from the new source flows through one portion of the graph until the old dotekaet Photo T, it flows from the source to the old S, then flows through another portion of the graph, and finally arrives at the beginning of this edge and into a new stock T '. That is, if we find in this modified maximum flow graph (and the drain gets the right amount of flow, ie the sum of all values of L i - otherwise the flow rate will be lower, and the answer simply does not exist), we simultaneously find flow in the original graph, which will satisfy all constraints minimum, and, of course, all the constraints of the maximum.
Solution of Problem 2
Note that on the edge of an old run-old source with a capacity of INF flows all the old stream, ie, bandwidth of the edge influences the value of the old stream. For sufficiently large values of the capacity of this edge (ie INF) old flow is unrestricted. If we reduce the bandwidth, then, after a certain time, and will decrease the value of the old stream. But too small value of the flow rate will be insufficient to ensure that the constraints (to the minimum flow along the edges). Obviously, you can usebinary search on the value of INF , and find it is the smallest value for which all constraints are satisfied yet, but the old thread will have a minimum value.
The flow of minimum cost (min-cost- flow). Algorithm increasing ways
Given network G, consisting of N vertices and M edges. Each edge (generally oriented, but in this connection see. Below) contains the capacity of the (non-negative integer), and the cost per unit of flow along this edge (an integer). Column Set the source S and drain T. gives some K value stream, find the flow of this magnitude, with among all flows of this magnitude to choose the least-cost flow ("task min-cost-flow").
Sometimes the task of putting a little bit different: it is required to find the maximum flow of the lowest value ("task min-cost-max-flow").
Both of these problems are solved effectively increase the algorithm described below ways.
Description
The algorithm is very similar to the Edmonds-Karp algorithm for calculating the maximum flow .
The simplest case
Consider to begin with the simplest case when the graph - oriented, and between any pair of vertices is at most one edge (if there is an edge (i, j), then the edges (j, i) should not be).
Let U ij - bandwidth ribs (i, j), if there is an edge. Let C ij - the cost per unit of flow along the edge (i, j). Let F ij - the value of the flow along the edges (i, j), initially all the fluxes are zero.
Modify the network as follows: for each edge (i, j) added to the network so-
called reverse edge (j, i) with a capacity of U ji = 0 and the value of C ji = - C ij . Because, by assumption, the edges (j, i) to this network was not modified in such a way that the network is still not multigraph. In addition, all along the algorithm will support true condition: F ji = - F ij .
Define residual network for a certain fixed flow F as follows (in fact, just as in the Ford- Fulkerson algorithm) network owned by only the residual unsaturated ribs (i.e. in which F ij <U ij ), and a residual bandwidth of each such as ribs UPI ij = U ij - F ij .
Actually algorithm min-cost-flow is as follows. At each iteration, the algorithm finds the shortest path in the residual network from S to T (the shortest relative value of C ij). If the path is not found, then the algorithm terminates, the flow F - sought. If the path has been found, we are increasing the flow along it as much as possible (ie, pass along this path, we find minimal residual capacity MIN_UPI among the edges of the path, and then increase the flow along each edge of the path on the value MIN_UPI, do not forget to reduce the same amount of reverse flow along the edges). If at any point the flux has reached the K (given to us by the condition of the flux), we will also stop the algorithm (it should be noted that while in the last iteration of the algorithm by increasing the flow along the path you need to increase the flow to a value such that the final flow not exceeded K, but this is easily done).
Easy to see that if we put K equal to infinity, then the algorithm finds the maximum flow of minimum cost, ie the same algorithm without modification solves both problems min-cost- flow and min-cost-max-flow.
The case of undirected graphs, multigraphs
The case of undirected graphs and multigraphs conceptually no different from the above, therefore, the actual algorithm will work on these graphs. However, there are some difficulties in the implementation, which should be addressed.
Undirected edge (i, j) - is actually two oriented edges (i, j) and (j, i) with the same bandwidth and cost. Since the above algorithm min-cost-flow is required for each undirected edges to create the opposite edge to him, the result is that the non-oriented edge is split into 4 oriented ribs, and we actually get the case multigraph .
What problems cause multiple ribs ? Firstly, the flow rate of each of multiple edges must be maintained separately. Second, when looking for the shortest path, be aware that it is important what kind of select multiple edges when you restore the path to the
ancestors. Ie instead of the usual array of ancestors for each vertex, we should keep the top of the parent and the number of edges on which we have come out of it. Thirdly, when the flow along the edge of a need according to an algorithm to reduce the reverse flow along the rib. Since we can have multiple edges, you'll need to keep the number of each edge ribs, reverse it.
Another difficulty with undirected graphs and multigraphs not.
Operating time analysis
By analogy with the analysis algorithm Edmonds-Karp, we get the following estimate: O (NM) * T (N, M), where T (N, M) - the time required for finding the shortest path in a graph with N vertices and M edges. If this is implemented using the simplest version of Dijkstra's algorithm , the entire algorithm min-cost-flow will estimate O (N 3 M) , however, Dijkstra's algorithm will have to modify it to work on graphs with negative weights (called Dijkstra's algorithm with potentials ).
Instead, you can use the algorithm of Leviticus , which, although asymptotically much worse, but in practice it works very quickly (in about the same time as the Dijkstra's algorithm).
Implementation
Here is an implementation of the algorithm min-cost-flow, based on the algorithm of Leviticus .
The input to the algorithm is supplied network (undirected multigraph) with N vertices and M edges, and K - value stream you want to search. The algorithm finds the minimum flow value of K value, if one exists. Otherwise, he finds the maximum value of the flow of minimum cost.
The program has a special feature to add a directed edge. If you need to add a non-oriented edge, then this function should be called for each edge (i, j) twice by (i, j) and of (j, i).
const int INF = 1000 * 1000 * 1000;
struct rib {
int b, u, c, f;
size_t back;
};
void add_rib (vector <vector <rib>> & g, int a, int b, int u, int c) {
rib r1 = {b, u, c, 0, g [b] .size ()};
rib r2 = {a, 0, -c, 0, g [a] .size ()};
g [a] .push_back (r1);
g [b] .push_back (r2);
}
int main () {
int n, m, k;
vector <vector <rib>> g (n);
int s, t;
... Read Count ...
int flow = 0, cost = 0;
while (flow <k) {
vector <int> id (n, 0);
vector <int> d (n, INF);
vector <int> q (n);
vector <int> p (n);
vector <size_t> p_rib (n);
int qh = 0, qt = 0;
q [qt ++] = s;
d [s] = 0;
while (qh! = qt) {
int v = q [qh ++];
id [v] = 2;
if (qh == n) qh = 0;
for (size_t i = 0; i <g [v] .size (); ++ i) { rib & r = g [v] [i];
if (rf <ru && d [v] + rc <d [rb]) { d [rb] = d [v] + rc;
if (id [rb] == 0) { q [qt ++] = rb;
if (qt == n) qt = 0;
}else if (id [rb] == 2) {
if (--qh == -1) qh = n-1;
q [qh] = rb;
}
id [rb] = 1;
p [rb] = v;
p_rib [rb] = i;
} }
}if (d [t] == INF) break;
int addflow = k - flow;