Ford-Fulkerson algorithm

By now, you are already familiar with the problem of finding the maximum flow in a network. Moreover, you even know the gist of the most popular algorithms that solve it. However, sometimes in order to use an algorithm successfully in various real-life tasks, a deeper understanding is needed. So, why not dive into exploring the Ford-Fulkerson algorithm?

Algorithm

Before discussing the steps of the algorithm, let's remember the definitions of some important structures that are used in it.

First off, a flow network is a directed graph, which has a source and a sink, and each edge of which has flow and capacity. Secondly, a residual graph is used in this algorithm. It is a graph, each edge of which has a residual capacity assigned to it. Don't forget that the residual capacity is the difference between the capacity and the flow of an edge. Finally, an augmenting path is a path from the source to the sink that consists only of edges with a positive residual capacity.

Now, it is time to move on to the algorithm. Do you recall from previous topics that the word flow can have many meanings? For this very specific reason, this topic will use different symbols to denote different types of flow.

Let $f(v, w)$ be the flow of the edge that connects vertices $v$ and $w$. Additionally, $f_{aug}$ stands for the flow of an augmenting path found on every iteration of the algorithm. The steps of the algorithm are as follows:

1. Initialize the flows of the edges with $0$.
2. Find any augmenting path and determine its flow, $f_{aug}$. Let $x_1, x_2, ..., x_n$ be the residual capacities of the edges this path consists of. Then obviously $f_{aug} = min(x_1, x_2, ..., x_n).$Indeed, the flow that you send through the augmenting path equals the minimal residual capacity of its edges. It is pretty straightforward, isn't it?
3. Update the flows of the edges of the network. For every edge that goes from node $v$ to a node $w$:

   $f(v, w) = f(v, w) + f_{aug}$

   $f(w, v) = f(w, v) - f_{aug}$
4. Repeat steps 2 and 3, while there is an augmenting path in the residual graph of the network.

That's it! Doesn't sound too difficult, does it?

However, as you may have noticed, there is one detail that the algorithm lacks: it doesn't tell you how exactly you should find an augmenting path. This is why sometimes it is called not the Ford-Fulkerson algorithm, but the Ford-Fulkerson method. Just as any other method, it has some implementations, one of which is the Edmonds-Karp algorithm.

This algorithm is basically the same as the Ford-Fulkerson one. There is only one difference: in the Edmonds-Karp algorithm, you push the flow through the augmenting path that is the shortest and not just through any one. In this case, the shortest means consisting of the smallest number of edges. For example, imagine that you have the following residual graph:

It has three augmenting paths: A-B-C-D, A-B-D, and A-D. If you use the Ford-Fulkerson algorithm, you may choose any one of them. In the Edmonds-Karp algorithm, however, you would choose A-D, as it is the shortest one.

Example

Now, let's look at how the algorithm would work for the following network. The numbers near each edge are capacities.

As mentioned above, the Ford-Fulkerson algorithm doesn't determine the exact way you should select each augmenting path. Therefore, if you try to find the maximum flow yourself, don't get scared if the flows of the edges differ from the ones in the example at some point. The main thing here is to find the correct total flow of the network.

After each step, you will see a picture of the network on the left and the residual graph on the right. In the beginning of the algorithm, the flow of each edge in a network equals $0$.

So, let's choose the first augmenting path. Let it be A-B-C-E. It goes through the edges AB, BC, and CE with residual capacities $7$, $8$, and $5$, respectively. Therefore, the maximum flow you can send through it is $5$, as it is the smallest capacity among them.

Now that the flows of the edges are updated accordingly, it's time to check if there are any more augmenting paths. Indeed, there are several of them: A-B-E, A-C-B-E, A-D-C-B-E. Let's look at A-B-E. The flow sent along the path this time is the following: $f_{ABE} = min(2, 10) = 2.$

You can see that no more flow may be pushed through the edges AB and CE. You wouldn't be able to find any other path if you looked only at the network itself. However, there is a residual graph and you can still find some augmenting paths in it. Let's choose the path A-C-B-E. The flow equals $min(4, 5, 8) = 4.$

There is only one augmenting path left in the residual graph, therefore, there are no options here. Let's push the flow of $1$ along the path A-D-C-B-E.

Hooray, no augmenting paths are left, which means that you've finally found the maximum flow of the network, which equals $12$.

Complexity and correctness

Given $f$ is the maximum flow and $E$ is the number of edges in a network, the complexity of the algorithm is $O(fE)$, which may look a bit unusual. Why is it like this? Imagine that you have a network that looks like this:

The worst-case scenario for it could be the following: first you find an augmenting path A-B-C-D-E, and then the path A-D-C-B-E.

As you can see, on each step you find an augmenting path with the flow of $1$. You repeat these steps on and on, leading to $f$ iterations in total. The complexity of finding an augmenting path is $O(E)$, therefore, the complexity of the whole algorithm is $O(fE)$. As for the Edmonds-Karp algorithm, its complexity doesn't depend on the maximum flow and equals $O(VE^2)$, where $V$ is the number of vertices and $E$ is the number of edges.

You already know how the algorithm works and what its complexity is. However, have you wondered why the algorithm works at all? In other words, why is the result found at the end of the algorithms the maximum flow possible?

First thing you need to understand is whether the algorithm terminates at some point. Indeed, it does, as the capacities of the edges are finite, so the flow that is pushed through them can't be increased forever.

The next question: why is the total flow of the network that the algorithm finds actually the biggest one possible? Suppose it is not. Consequently, an augmenting path can be found. However, in this case, the algorithm would still be running, because, as you remember, it stops only when there are no more augmenting paths from the source to the sink. Therefore, our assumption is wrong, and the flow found by the Ford-Fulkerson algorithm is maximum for the network.

Conclusion

To sum up, let's go through the main points of the topic:

• The Ford-Fulkerson algorithm is used to solve the maximum flow problem.
• The idea behind the algorithm is the following: you find the augmenting paths in a residual graph and sum the flows of these paths. When there are no such paths left, the algorithm stops.
• As the way of choosing augmenting paths is not specified, the Ford-Fulkerson algorithm is sometimes called the Ford-Fulkerson method. The Edmonds-Karp algorithm is an implementation of it.
• The complexity of the Ford-Fulkerson algorithm is $O(fE)$, where $f$ is the maximum flow and $E$ is the number of edges in a network.
• The complexity of the Edmonds-Karp algorithm is $O(VE^2)$, where $V$ is the number of vertices and $E$ is the number of edges.
• For some networks with non-integer capacities, the Ford-Fulkerson algorithm may not terminate.