Geekly Articles each Day
📜 ⬆️ ⬇️

Maximum flow minimum cost

The transport problem (classical) is the problem of the optimal plan for the transport of goods from warehouses to consumption points in vehicles.

For a classical transport problem, two types of tasks are distinguished: the cost criterion (achieving a minimum of transportation costs) or distances and the time criterion (a minimum of time is spent on transportation).

There is a lot of text under the cut, because It tells one of the options for solving this problem “in pictures” for those who have little knowledge of graphs . Listing attached.
')

On Habré somehow slipped an article where the question was raised, and whether the article about the basic algorithms. I decided to respond to the requests and tell a little about the algorithms on the graphs and their practical application. I did not know what level of knowledge to rely on, so I chose one relatively complex and theoretically practical algorithm, so that the article was at least partially applied. At the same time I will try to tell you what is available even for those who are not particularly familiar with graphs.

Problem (fairy tale): You are the owner of a factory producing the “Product”, and recently you were lucky enough to conclude a contract with a large firm located in another city for the supply of goods to their retail network. Since it is very far away (in Vladivostok), goods will have to be delivered by air. During telephone conversations, the Partner asked, “ but how much supply can we expect per day? ". You thought ... You have your own trucks (truckers) engaged in transportation. The airport is far away. After reviewing the accumulated traffic statistics, you found out that there are some limitations in transportation in your own area: there are cargo inspection points, weight control points on the roads, and some roads are being repaired. All this is called the " bandwidth " of the roads per day. Based on these conditions, you need to know: how many boxes of “Goods” per day can you bring to the airport? At the same time, you want to effectively conduct business and deliver the goods by the shortest routes, because This is the wear of tires, mechanisms, depreciation costs in general.

Total: how many boxes can you transport to the airport per day, taking into account the capacity of the roads, while keeping the total distance of the routes to be minimal?

Task - the most that neither is on the graphs. The solution will be built gradually.
There are no big problems, there are just a lot of little problems. (with)

Algorithms will, if I may say so, tell , because Online plenty of their descriptions.

Basic concepts. Graph? Baron?


The road map in our case is represented as a graph. The vertices are intersections, and the edges of the graph are roads. Ribs (roads) are attributed to their characteristics: the distance (to the next intersection), as well as throughput per day.

In code, graphs are either in the form of adjacency lists or adjacency matrices. For simplicity, we will use the adjacency matrix. If in the adjacency matrix at the intersection of [u] and [v] vertices is “1”, it means that these vertices (intersections) are connected by an edge (road). It is not necessary to designate exactly “1”; in a matrix it is very convenient to store other useful information attributed to an edge: for example, distance, and throughput (in a similar matrix).



The figure shows a matrix that is symmetric about the main diagonal, i.e. M [u] [v] = M [v] [u] . This means that we are given an undirected graph and we can pass along the edge in any direction (back and forth). If in the matrix M [u] [v] = 1 , and in the opposite direction M [u] [v] = 0 , then the graph is directed and you can go along the edge only from the vertex [u] to [v] .

The capacity of the roads we will be written in the matrix C [..] [..] , which generally speaking, is a directed graph. After all, the roads we need in order to drive from the "plant" in the direction of the "airport". A directed graph with given capacities (plant and airport) is called a network .

When for a graph it is necessary to calculate a certain characteristic, but not massively "from all-to-all", but let's say the distance from one vertex to the others, then it is much more convenient to use an array (less memory). Those. let's say in [u] the cell of the dist [..] array we will store the distance to [u] of the vertex from the “plant”. Similarly, we will use arrays when traversing the graph in order to mark already visited vertices ( mark ), record how many boxes were brought ( push ), and from where we arrived at the vertex ( pred ).

OK. Fine. We know how to convert our map into a graph. And how will we deliver the boxes to the airport? We need to be able to find a way from the “factory” to the “airport”. For this we will use ...

Bread first search algorithm, BFS.


For now, we only consider: the adjacency (neighborhood) of the vertices of the graph, without considering the capacities and distances.

BFS is one of the most basic algorithms that form the basis of many others.
A simple description (the figure will be below). We are now standing at some starting (plant) top [s] , from which only adjacent peaks are visible along the edges. And we really need to get to the top [t] , which is somewhere in this graph, as soon as possible. Next we do this. We look through the edges (namely, free roads) of our top of neighbors: are there [t] among them? If not, then we record all (first discovered) neighbors in the queue “you need to go there”. When we looked through all the neighbors - we mark our peak - “we have already been here”. We get the first unvisited top from the queue and go to it.

We continue the search in the same way. At the same time, those vertices that we once visited were ignored (not one step back). If on the way you met [t] - excellent, the goal is achieved!

In order not to drive into the same intersections several times, we will mark them in the mark array [..] . After inspecting the neighbors from [u] tops, we put a mark mark [u] = 1 - it means that we “have already visited” at the [u] -th intersection.

In the picture: at the vertices - ordinal numbers are written



After the completion of the algorithm, we obtain the following picture:



We note the main features:
Now we know how to find the way to transport our “Goods” boxes to the airport. Well ... Let's take them on the road, and mark it on the map. This mark - “how many boxes, on what road (edge) and in which direction we carry” we will call “ stream ”. We will mark this in the matrix ( flow ) F [..] [..] . Those. on the way from [u] to [v] we carry F [u] [v] boxes.

It's time to face the reality - you have to reckon with the “throughput”, which is denoted by the matrix ( capacity ) C [..] [..] . After all, on the way from [u] to [v] we can take no more than C [u] [v] boxes. That's a pity.

We arrived farsightedly. While we were looking for “airport” with BFS, while we noted “visited peaks” we also noted from which intersection we arrived - we recorded it in the pred array [..] . Those. we reached the vertex [v] from the vertex pred [v] . And just in advance they added another useful array: push [v] , i.e. how much we could “push” the boxes into the intersection [v] along some road [u] - [v] .
And kept it up to date: push [v] = min (push [u], C [u] [v] -F [u] [v]);

Due to this, until we have to “unwind” the trajectory from the “airport” to the “plant” once more in the reverse order, in order to calculate how many boxes we can carry out along this route.

Push [v] = push ["airport"] = flow = here! how many boxes were taken to the airport by the path found. Once we unwind the route and along all edges (roads), and add “flow” flow to all edges of the path.

But, even though the task deals with the natural quantities: the number of boxes, throughput and distances, you may still have to face a “ minus ” ...

Increase Flow (or Ford-Fulkerson Algorithm)


Now we take into account: the adjacency (neighborhood) of the vertices of the graph, the directed capacities of the edges, but we are not considering the distances yet.

When we increase the flow (of the boxes) from the top [u] to the top [v] , we naturally perform the operation: F [u] [v] + = flow , but in the opposite direction we reduce the flow F [v] [u] - = flow ; That's why. Such a situation is possible:

In the picture: on edges — signed (flow / throughput)



For the first time, having carried the stream to 3 boxes to the vertex [i] and found the edge [i] - [j] : We moved min (push [i], C [i] [j] - F [i] [j]) = min (3, 3-0) = 3 boxes, and marked it as F [i] [j] + = 3 , and in the opposite direction we set: F [j] [i] - = 3 .

The second time, being at the vertex [j] , we are trying to push min (push [j], C [j] [i] -F [j] [i]) = min (6, 0 - (- 3)) = min (6, 3) = 3 to the vertex [i] . Against the flow of +3 , we pushed -3 boxes and received a compensation flow on this road. But in the direction to the “airport” in the next iteration, we additionally sent the remaining 3 boxes.

Interpretation: from the warehouse [j] we called the warehouse [i] , and said: “Leave yourself your 3 drawers - find another use for them, we brought our 3 instead”. Although the algorithm itself has kindly found their use.

We continue to look for the stream:


We agreed to persistently continue to look for ways to the "airport", while we succeed, and carry boxes through them. Roughly speaking, this is called the maximum flow search algorithm, or the Ford-Fulkerson algorithm . And since we use BFS to “discover” new delivery routes, this is called the Edmonds-Karp algorithm.

When we “fill” the roads with the transportation of our boxes to the stop, we will answer the Partner with the question “How many boxes per day can we take to the airport?”. But it's time to think about their own depreciation costs ... Tires, gasoline, wear ...

It has already become clear that when searching by BFS for a graph, we will have to deal with negative values, such as reverse flow (and it has consequences in “financial terms”), even if we are talking about distances. In general, it’s time to take into account additionally the distances ...

Distances Hit the road, Jack!


It is time to finish this task entirely: adjacency (neighborhood) of the graph vertices, directed edge carrying capacities, distances.

We continue to run BFS until we load the roads with our drawers “all the way”:



Now look at what happened. We will check from the “airport”: if a box reached us at a distance of 15 km, then if we refused, then we would save 15 km. directions (ie, subtract 15), but if possible, try to find (attach) him another way of movement.

Let's try to walk along the edges in direct (on free roads) and back (pushing back and saving) directions from the “airport”:

In the picture: on the edges - signed (flow / throughput), and above - the distance



In the picture above, we found a “negative cycle” -6, still walking along accessible (free or pushing against the flow) ribs. By making one revolution in it, we can reduce the distance for the vertices participating in it by -6. This means that you can save on the delivery of crates transported in a cycle. Just letting the boxes "on the cycle." In the picture above, we will save 6 km. of the way.

Now we know how to solve the problem, but in order to detect these cycles ... Consider:

Bellman-Ford Algorithm


It is used to find the shortest distance from the vertex [s] to the other vertices. But unlike BFS, the short path will not be in the sense of the number of edges of the graph on this path, but in the sense of the summed “distance” along the edges of the path.

But we will need it not for this. One of its key features that distinguishes it from Dijkstra’s algorithm is that it is capable of working on graphs, where the weight of the edges can be given by a negative number. The algorithm can detect a side effect of such graphs — negative-value cycles. What we need!

The algorithm is somewhat more complicated. This implementation somewhat does not correlate with Cormen’s bible, but it also works fine. It looks a bit like BFS, so I will try to explain, starting from it.

Starting from a certain vertex, we scan adjacent vertices along the “accessible” edges, and try to improve the distance to them in the dist [..] array and make it as small as possible. This process is called “relaxation.” If we “felt” (along the edges) such vertices, then we update them with the distances and put their vertices into the queue “try to improve the graph from them”. Very similar to BFS! But we do not mark the vertices (“already visited”) and if we have to go to the same vertex twice, we will do it.

But the question is, are we ready for the fact that there will be “negative cycles” that you can always spin on, reducing the distance to the vertices? The process will not end. Therefore, the "inspection radius" of the vertices is limited by the number N (the number of the vertices themselves). This will be guaranteed enough to calculate the minimum distance to any vertex, and most importantly the algorithm will end in any case.

To do this, we place the first vertex in the queue, and after it the “stub”, thus denoting that there are vertices in the queue in the “inspection radius 0”. When, taking out the next peak from the queue, we suddenly reach our “stub” - we will install a new one, denoting the next “inspection radius”. Here, in general, and all the logic of the algorithm. =)

The improvement of the distance to the vertices is verified by the following inequality:
dist [v]> dist [u] + edge_cost (u, v)

In the picture: length on edges, and the shortest distance found at the moment in the tooltip.



Note the main features (as opposed to BFS):
Viewing the graph in "radius N (number of vertices)" ensures that for all vertices we have found the minimum distance. And nothing else to reduce. And if some of the vertices are “drawn” into a “negative cycle”, then it can be easily detected by checking for violation of equality. Indeed, in a cycle, the distances infinitely decrease:
dist [v]> dist [u] + edge_cost (u, v)

Therefore, if for the vertex [v] this inequality holds, it means that it participates in the negative cycle. What is needed! "Unwinding" from her the way in which we got into it, we will spin along (her) cycle.

All - cycle detected! It remains only to send a stream of boxes on it to "reverse", and thereby increase the efficiency of doing business.

Algorithm Maximum Flow minimum cost:




Everything. We call the Partner and let us know how many goods per day we will be able to deliver to him. And we think how to apply the money saved. =)

int C[MAX_N][MAX_N]; // " "
int F[MAX_N][MAX_N]; // " "
int P[MAX_N][MAX_N]; // " ()"
int push[MAX_N]; // [v]
int mark[MAX_N]; // ,
int pred[MAX_N]; // [v] ()
int dist[MAX_N]; // [v]
int N, M, s ,t; // - , ,
int max_flow;
int min_cost;

void file_read()
{
int u, v, c, p;
in >> N >> M >> s >> t; N++;

for ( int i = 0; i < M; i++)
{
in >> u >> v >> c >> p;
C[u][v] = c;
P[u][v] = p;
P[v][u] = -p;
}
}

int edge_cost( int u, int v)
{
if ( C[u][v] - F[u][v] > 0 ) return P[u][v];
else return MAX_VAL;
}

int check_cycles()
{
for ( int u = 1; u < N; u++)
for ( int v = 1; v < N; v++)
if ( dist[v] > dist[u] + edge_cost(u, v) )
return u;

return MAX_VAL;
}

void init()
{
for ( int i = 1; i < N; i++)
{
mark[i] = 0;
push[i] = 0;
pred[i] = 0;
dist[i] = MAX_VAL;
}
}

//

int bf( int s)
{
init();
queue< int > Q;
pred[s] = s;
dist[s] = 0;

Q.push(s);
Q.push(MAX_N);

int u, series = 0;
while ( !Q.empty() )
{
while ( Q.front() == MAX_N )
{
Q.pop();
if ( ++series > N ) return check_cycles();
else Q.push(MAX_N);
}

u = Q.front(); Q.pop();
for ( int v = 1; v < N; v++)
if ( dist[v] > dist[u] + edge_cost(u, v) )
{
dist[v] = dist[u] + edge_cost(u, v);
pred[v] = u;
Q.push(v);
}
}
}

// -

int bfs( int s, int t)
{
init();
queue< int > Q;
mark[s] = 1;
pred[s] = s;
push[s] = MAX_VAL;

Q.push(s);
while ( !mark[t] && !Q.empty() )
{
int u = Q.front(); Q.pop();
for ( int v = 1; v < N; v++)
if ( !mark[v] && (C[u][v]-F[u][v] > 0) )
{
push[v] = min(push[u], C[u][v]-F[u][v]);
mark[v] = 1;
pred[v] = u;
Q.push(v);
}
}

return mark[t];
}

// -

void max_flow_ff()
{
int u, v, flow = 0;

while ( bfs(s, t) )
{
int add = push[t];

v = t; u = pred[v];
while ( v != s )
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
flow += add;
}

max_flow = flow;
}

//

void min_cost_flow()
{
max_flow_ff();

int u, v, flow = 0;
int add = MAX_VAL;
int neg_cycle;

neg_cycle = bf(t);
while ( neg_cycle != MAX_VAL )
{
v = neg_cycle; u = pred[v];
do
{
add = min(add, C[u][v]-F[u][v]);
v = u; u = pred[v];
}
while ( v != neg_cycle );

v = neg_cycle; u = pred[v];
do
{
F[u][v] += add;
F[v][u] -= add;
v = u; u = pred[v];
}
while ( v != neg_cycle );

neg_cycle = bf(t);
}

for ( int u = 1; u < N; u++)
for ( int v = 1; v < N; v++)
if ( F[u][v] > 0 )
min_cost += F[u][v] * P[u][v];
}

void file_write()
{
out << max_flow << endl;
out << min_cost << endl;
}

void main()
{
file_read();
min_cost_flow();
file_write();
}

* This source code was highlighted with Source Code Highlighter .


// And if we took the following conditions: vertices - intersections of streets, edges - roads, throughput - number of lanes (allowed speed, etc.) minus the current number of cars on these roads. Let's find the maximum flow from the street “A” to the street “B” - why are there no roads in the city currently free? Of course, you need to take into account much more parameters, but the basis is the graphs. It is interesting. =)

Total


Do not scold me much, please

Starting a post about the graphs, I did not know what level of competence to count on: I decided not to tell just about, say, Dijkstra, because its accessible description is very easy to find on the network . Suddenly every second person writes it by heart. But just remember that Habra-comrades were interested in precisely the practical side of these algorithms. Therefore, he took the “spherical” puzzle and in its terms tried to visually tell about the graphs.

I hope that someone will be interested to read about the graphs and an example of their use. Moreover, writing an article made me want to remind students (schoolchildren) or graduate students teaching them programming about one of the most famous ACM ICPC programming competitions! Those who have not yet decided (did not dare) in the early courses of the university assemble a team, stay up late in computer classes, discuss the asymptotics of the algorithms, come up with solutions and counter examples for them. Algorithms are interesting and a good reason to get together, and the experience of a team game is priceless. Join now!

Source: https://habr.com/ru/post/61884/

More articles:


All Articles