The Ford-Fulkerson Algorithm
(Page 1 of 4 )
The world is full of problems. Everything around us works to cause or solve some problems for us. Solving problems is a daily necessity. Of course, we deal with problems that directly relate to us. An issue like this is the flow problem inside a flow network, so how do we solve it? The answer is “The Ford-Fulkerson algorithm,” and finding out just how it works will be our goal today.
Before I venture any deeper into this, the first and most important question is: what problems will this solve? What benefit will you get from reading and understanding this article? You will be amazed by how many real life problems will gain an optimal and good solution from this algorithm. However, for a prime example consider this.
Let there be a water network system. The question is, how big we should make the water pipes so that everyone can receive at any time a given amount of water? Add to this the caveat that we do not want to spend extra money on pipes that are larger than required. From this problem, it's just one step to find out if the elimination of a given military headquarters in Vietnam poses a major threat to us.
To debate every single aspect of network flow algorithms (we are talking manly about the Ford-Fulkerson algorithm and how to use it for solving different issues), we will split the topic into two articles. In this one, the central objective will be to just understand the algorithm; how to adapt it to more complex problems is the topic for the next article.
Furthermore, you should know that this is part of a larger article series of mine about graphs and algorithms; in fact, this is the eleventh article in a thirteen-part series. I already covered topics such as the definition of a graph, how we store graphs in memory, and the breadth-first search. I will not explain these areas again, and you need to know them to understand this article. If you missed those articles, and are not otherwise familiar with these concepts, read the articles at the links shown above before continuing.
What is a flow network then? It is a connected graph with weighted edges that are directed. Additionally, flow networks have a single source vertex (from which there are only outgoing edges) and a single terminal vertex (a drain vertex, which will have only incoming edges). This way we can perceive it as a network system from which the source vertex is pumping water into the network, and the terminal is collecting it and draining it out.
Next: The Theory >>
More Code Examples Articles
More By Gabor Bernat
