Ford-Fulkerson Algorithm Technische Universität München

Introduction
Create a graph
Run the algorithm
Description of the algorithm
More

The maximum s-t flow has a value of 6

The Maximum Flow Problem

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.

What do you want to do first?

Download Graph

Legende

	Node
	Edge with capacity 10

Legende

Which graph do you want to execute the algorithm on?

Start with an example graphs:

Select

Modify it to your desire:

To create a node, double-click in the drawing area.
To create an edge, first click on the output node and then click on the destination node.
The edge weight can be changed by double clicking on the edge.
Right-clicking deletes edges and nodes.

Download the modified graph:

Download

Upload an existing graph:

occured when reading from file:

the contents:

What next?

Download Graph

Legende

	Node
	S/T node
	Edge with capacity 10 and flow 7.
	Edge in the residual graph.
	Edge on augmenting path.

Legende

Algorithm status

rewind fast forward

Explanation
Pseudocode
Variable State

First choose a source node

Click on a node to select it as the source/starting node s

Then choose a target node

Click on a node to select it as the target/sink node t

Ford-Fulkerson maximum flow algorithm

Now the algorithm can begin. Click on next to start it

Initializing the flow

Set f(e) = 0 for all edges in the graph.

Entering the main loop

The main loop repeatedly looks for augmenting paths to increase the total flow and adds them to the total flow.

Path search

We now look at the residual graph associated with the current flow. The algorithm looks for an augmenting path that connects s and t.

Check path

Check if the search is finished. Either finish by expanding t expanded, run out of nodes, or continue expaning.

Expand current node

Pick the next node from the queue to expand and mark the neighbours. Unvisited neighbours are added to the expansion list.

Init path reconstruction

Clear the path and start reconstructing from t.

Apply augmenting path

The flow is increased along the augmenting path until one edge in the residual graph saturates.

Finished

The algorithm terminated with a maximum flow value of:

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(s,t)

augmentation ← min(e ∈ path)

FOR {e ∈ path}

flow(e) ← flow(e) + augmentation

END

Variable status

path	augmentation
{}	0

Switching the tab stops the execution of the algorithm.

You can open the app in another browser window,f you want to keep reading in parallel.

Maximum Flows

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?

Input: Network graph G=(V,E), cost function c'(e)
Output: flow mapping f(e)


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²)
Algorithm of Dinic: O(V²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.

Web resources

Where can I find more information about graph algorithms?

Other graph algorithms are explained on the Website of Chair M9 of the TU München.

Studying mathematics at the TU München answers all questions about graph theory (if an answer is known).

A last remark about this page's content, goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the mathematical optimization of applied problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the daily research conducted at the chair reaches far beyond that point). These pages shall provide pupils and students with the possibility to (better) understand and fully comprehend the algorithms, which are often of importance in daily life. Therefore, the presentation concentrates on the algorithms' ideas, and often explains them with just minimal or no mathematical notation at all.

Please be advised that the pages presented here have been created within the scope of student theses, supervised by Chair M9. The code and corresponding presentation could only be tested selectively, which is why we cannot guarantee the complete correctness of the pages and the implemented algorithms.

Naturally, we are looking forward to your feedback concerning the page as well as possible inaccuracies or errors. Please use the suggestions link also found in the footer.

To cite this page, please use the following information:

Title: Ford-Fulkerson Algorithm
Authors: Quirin Fischer, Wolfgang F. Riedl; Technische Universität München
Link: https://www-m9.ma.tum.de/graph-algorithms/flow-ford-fulkerson