The Ford-Fulkerson Algorithm - The Theory
(Page 2 of 4 )
To help you understand this better, I will need to further explain the terms we will use. We will name a road a sequence of vertexes (and as a sequence of edges also) that do not contain the same vertex twice. The edges still connect one after another. However, we will ignore their direction.
On this road, we can differentiate between two types of edges. There are edges that point in the same direction in which we would walk the network (so they point ahead), and edges indicating the opposite direction (therefore pointing backward).
A road like this is called saturated if all of the forward-pointing edges along it have a capacity (weight of the edge), and the flow currently going through them is equal, and if the backward-pointing edges have a current flow greater than 0.
An improving road is one through which all of the edges are yet not saturated. Therefore, we can increase the overall flow of the network through this road while we also increase the same trait of the edges, and if we make the right amount of improvement, a single edge at least will be saturated.
Of course, while we make the improvement we need to decrease the current flow on the backward- pointing edges and increase it on the forward-pointing ones. What is the maximum amount by which we can increase this? Forward-pointing edges we can improve, at most, by the capacity of the edge minus the current flow, while backwards-pointing edges can be improved by the amount we can decrease that edge.
The final answer to our question will be the minimum of these maximum values. The fact that we can increase it by this amount is guaranteed by the fact that we can increase the amount coming out from the source by any value, and the rest will be at most saturated after we make the improvement.
How will the backward-pointing edges put their own share to increasing the overall flow that we can pump into a network? The answer lies in the observation that when the least comes back, the most will go ahead. Consider that the edge between u and v is backward-pointing. Think of it as if, at vertex u, the amount just vanishes and appears at vertex v.
In reality, of course this amount will have to make its road through the outgoing edges of the u vertex. Eventually, they will reach vertex v by the incoming edges of that node.
Now we can state the Ford-Fulkerson algorithm. We start with a flow through all of its edges; the current flow value is zero. While we can find any improved road from the source vertex to the terminal node, repeat the following steps. Search for the improved road.
You will determine the maximum value by which we can improve on it. Make the enhancement. The maximum flow value that can handle the network is the sum of all the improvements.
Next: Implementation issues >>
More Code Examples Articles
More By Gabor Bernat
