The Ford-Fulkerson Algorithm - Implementation issues
(Page 3 of 4 )
While the algorithm presented on the previous page will indeed provide a correct answer, the order in which we take the improved roads to perfect our solution matters. The difference is in execution time and the number of steps required to solve it.
According to the Edmon-Karps Theorem, if at every step we make the enhancement through the roads that contain the minimum number of roads, the Ford-Fulkerson Algorithm will have its solution in a polynomial time. For the proof of this, look up the Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein book titled Introduction to Algorithms.
Therefore, we will store the data in two ways before we let the algorithm start. We will use a neighbor list with the modification that we will ignore the direction of the edges, and have another item showing us the sum of the incoming and outgoing edges to a specific vertex.
The second structure is a neighbor matrix where, at position u and v (representing in practice the edge from u to v), we will store first the current flow of the edge, and the capacity of the edge. While the capacity of the edge will be the read-in data if we have it, one, and otherwise minus one, the current flow value is, for all of them, zero.
We will do the minimum road search with a modified version of the breadth first search. The search will use the neighbor list that eliminates the direction of the edges; however, we will only consider edges that are not yet saturated. This assures us that we can make the enhancement through the found road.
To get the amount by which it can improve through an edge, the search will use the neighbor matrix. Inside of this we can deduce if the edge from u to v is incoming or outgoing. If a forward-pointing exists and it still has not reached its capacity, we can travel ahead on it.
The other valid option is that there exists an incoming edge. Moreover, this has a flow value greater than zero. If there exist both types, first consider the outgoing edges, and after that, the incoming ones. If we find an edge that is valid, we save its parent. The search will start out from the source and will end up in the terminal node. Now we can start a little recursion on this array to find and make the improvement at once.
While we go deeper on the recursion, we can calculate the maximum value for each vertex. Pick out of them the minimal value. On the back-pointing branch of the recursion, make the improvement as well. To the forward-pointing edges we will add it, and from the backward-indicating ones, subtract it. An example of improvement for the graph:
The first step is:
If the minimal value found with this approach is zero, there are no more roads that can provide improvement, and the Ford- Fulkerson Algorithm is finished. Add up all the values with which we enhanced our network, and the overall flow value is also given.
Next: The C Code >>
More Code Examples Articles
More By Gabor Bernat
