A typical application of graphs is using them to represent networks of transportation infrastructure e.g. for distributing water, electricity or data. In order capture the limitations of the network it is useful to annotate the edges in the graph with capacities that model how much resource can be carried by that connection.

An interesting property of networks like this is how much of the resource can simulateneously be transported from one point to another - the maximum flow problem.

This applet presents the Ford-Fulkerson algorithm which calculates the maximum s-t flow on a given network.

Graphs can be used to formulate mathematical models for many different applications. One particular type of problem deals with networks that transport some kind of resource from one endpoint to another - think water, electricity, or data.

In general this type of model is called flow problem. A flow problem is defined by the graph representing the network structure, annotated with some more information. For every edge of the graph it is necessary to specify the maximum amount of resource that can be shifted along this edge - it's capacity c(e). It is also necessary to pick a source and a target node for the flow.

A solution of a flow problem is an assignment of how much flow should move along each edge. A valid flow has to fulfill two constraints: Every edge can carry at most its full capacity. Furthermore, when aggregating the flow through a node of the network, the incoming and outgoing flow has to be equal at all nodes (except the source and the target).

The most basic flow problem is that of finding the maximum possible flow: how much resources can be transported from one node to another.

Idea of the Algorithm

The Ford-Fulkerson Algorithm computes a maximum flow in a iterative manner by starting with a valid flow, and then making adjustments that fulfill the constraints and increase the flow.

An important concept to uderstand the algorithm is the residual graph. This is a graph generated by calculating how the flow along each edge can be modified - each edge in the network graph is replaced by up to two new edges, a forward edge with the same direction that that signifies how much the flow can be increased, and a backward edge storing how much the flow can be reduced.

The algorithm starts with a empty flow (which is always valid) and then repeatedly finds paths in the residual graph from source to target. Adding just enough flow along the path to saturate one edge, which is the one with the lowest capacity, keeps the contraints on the flow fulfilled and strictly increases the flow. These are called augmenting paths

How to Find Paths in the Residual Graph

The Ford-Fulkerson method does not explicitly state how to find the augmenting paths, and works with and path finding algorithm. However, the choice of strategy has an impact on the (worst case) runtime of the algorithm. Depth-first search is a comparatively bad choice, using Breadth-first search (BFS) gives better results. This specific modification is called the Edmonds-Karp algorithm. Another variant with even better performance is the algorithm of Dinic.

What now?

Create a graph and play through the algorithm

What is the pseudocode description of the algorithm?

s ← pick(v)
t ← pick(v)
BEGIN
(* Initializing the flow *)
FOR { e ∈ E } DO
f(e) ← 0
(* Main Loop *)
WHILE path might exist DO
path ← FIND_PATH_IN_RESIDUAL()
IF path EXISTS;
augmentation ← min(c'(e) | e ∈ path);
FOR {e ∈ path}
f(e) ← f(e) + augmentation
END

How efficient is the Algorithm?

The runtime of the algorithm is mostly determined by the path selection strategy. The different variants result in the following complexity classes:

Depth-first search: O(V max(f))

Breadth-first search (Edmonds-Karp): O(VE^{2})

Algorithm of Dinic: O(V^{2}E)

References

Literature

[FF56]

Ford, L. R.; Fulkerson, D. R. (1956). "Maximal flow through a network". Canadian Journal of Mathematics. 8: 399. doi:10.4153/CJM-1956-045-5

[Jun13]

Dieter Jungnickel. Graphs, networks and algorithms. Fourth. Bd. 5. Algorithms and Com- putation in Mathematics. Springer, Heidelberg, 2013, S. xx+675. isbn: 978-3-642-32277-8; 978-3-642-32278-5. doi: 10.1007/978-3-642-32278-5. url: http://dx.doi.org/10. 1007/978-3-642-32278-5.

A last remark about this page's goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the optimization of mathematical problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the research conducted daily at the chair reaches far beyond that point). This page shall provide the possibility pupils and students to understand and fully comprehend the algorithms (which are of importance also in daily life).

To cite this page, please use the following information:

Title: Ford-Fulkerson Algorithm

Authors: Quirin Fischer, Wolfgang F. Riedl; Technische Universität München