Number algorithm

About requesting network maximum stream and minimum score algorithm:

A given one direction map G = (V, E), regarding the edges in the figure as a pipe, there is a weight on each side, indicating the flow rate of the pipe. Given the source point S and the discharge point T, now suppose there is a water source at S, there is a water storage in t, asking the maximum water flow from S to T. This is called a network stream problem. Description by mathematical language is:

Set g = (v, e) is a stream network, set C (U, V)> = 0 to indicate the flow rate of the pipe from U to V. Set S is the source, T is the exchange. G The stream is a function f: V × V → R, and meets the following three characteristics:

1. Capacity restriction: For all U, V ∈ V, require f (u, v) <= C (u, v)

2. Abcayness: For all U, V ∈ V, require f (u, v) = - f (v, u)

3. Circular session: For all u V - {s, t}, required σ f (u, v) = 0; v∈V

f (u, v) is called a network stream from the nodes U to V, which can be positive or negative. The value of stream F is defined as:

| f | = σ f (s, v)

V∈V

That is, the sum of all flows from the source.

The maximum current problem is to find the maximum stream of the fixed network. Network flow issues can be summed up as a special linear planning issue.

Finding the basic way to find the maximum stream is the Ford-Fulkerson method, which has a variety of implementations. Its basic idea is from a possible stream F. Find a way to improve the stream P, then follow the P, Attempting to find new feasible streams to find the improved road, so repeated until the maximum flow. Now you have to find the minimum flow of the minimum cost, you can prove that if f is the smaller of the flow rate of V (f), and P is the minimum cost of all the cost of f, along the P To adjust f, the obtained active stream F 'must be the minimum cost stream in all the active streams of V (f'). In this way, when F is the maximum flow, he is the minimum flow of the minimum cost.

Note that the unit traffic costs B (I, J) of each side are ≥0, so f = 0 must be the minimum cost stream of traffic 0, which is always

From f = 0, you will find the maximum flow of minimum costs. In general, it is known that f is the minimum cost stream of traffic V (f), and the remaining problem is how to find the minimum cost of F. To this end, we turn each arc in the original network into two arcs:

1. The forward arc , capacity C and cost B are constant, and the flow f is 0;

2. The rear-to-arc , the capacity C is 0, the cost is -b, the flow f is 0;

Set a parameter CT on each vertex, which represents the cost of the source point to the path to the vertex. If we draw a minimum fee about F. The CT value of each vertex on the road is minimal to other modified roads. Every time you find the minimum cost, you can improve the road, the source point CT is 0, the CT of the other vertices is ∞.

Set the ship's transportation fee, due to F = 0, then COST = 0, we find a minimum fee about F. Cost ← COST σB (E) * D, (where E∈P, D is the improved amount of P to cumulate flow of transportation

Add amount. Obviously, when seeking the minimum flow of the minimum cost, Cost has become the maximum flow of transportation.

In addition, the Boolean variable Break can improve the extension flag of the road, after searching for every vertex in the network.

If BREAK = true indicates that the road can be improved, it is also necessary to re-search the vertex in the network; otherwise, explain the minimum cost of the minimum fee has been found or the maximum stream has been obtained.

Here is the pseudo code of the algorithm:

COST ← 0;

Repeat

Improve the road withdrawal;

The CT value of the source point is 0 and enters the improved path;

Repeat

Break ← false;

For u ← 1 to n DO

Begin

Analysis of all arc ;

IF ( flow can be improved) AND (source point to U with passage) AND (CT value of U, V> CT value) THEN

Begin

Break ← True;

V 's CT value ← U of CT value ;

V Enter the label for improved the path;

END IF

End for

Until Break = FALSE

IF Meeting Number THEN

Begin

Departure from the coming point to fix the traffic of the road;

COST ← COST σB (E) * D (where E∈P, D is the improved amount of P);

END IF

Until setpoint unbailed;

It can be seen that the above algorithm is almost the same as the maximum streaming Edmonds-Karp label algorithm, because both algorithms use width priority search to find an increase in the channel, so complexity is the same, all O (VE), where V Is the number of nodes, E is the number of edges.