A maximum flow Ford-Fulkerson Algorithm Technische Universität München

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?


node Node
edge Edge with capacity 10


Which graph do you want to execute the algorithm on?

Start with an example graphs:

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:


Upload an existing graph:


occured when reading from file:

the contents:


What next?


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


Algorithm status

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.

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.


The algorithm terminated with a maximum flow value of:

s ← pick(v)

t ← pick(v)


(* Initializing the flow *)

FOR { e ∈ E } DO

f(e) ← 0

(* Main Loop *)

WHILE path might exist DO

FOR {e ∈ path}

flow(e) ← flow(e) + augmentation


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.