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


Network \(N = (G, c, s, t)\) with maximum flow f * \( = 6\)


The Maximum Flow Problem

-Searching for maximum flows

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 flow from a source to a target on a given network.

What do you want to do first?


Legende

node Node
edge Edge with capacity 10

Legende

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. Negative weights are not allowed
  • Right-clicking deletes edges and nodes.

Annotation: Double edges are not allowed. Look up the description of the algorithm for the explanation!

Download the modified graph:

Download

Upload an existing graph:

A

occured when reading from file:

the contents:

                    

What next?

Legende

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.

Legende

Algorithm status

First choose a source node

Click on a node to select it as the source \(s\).

Intuitively is this source the start node from which the flow is sent.

Then choose a target node

Click on a node to select it as the target or sink \(t\).

Intuitively is this target the goal node to which the flow is sent.

Ford-Fulkerson: a maximum flow algorithm

Let now \(G = (V,E)\) be the created graph with the respective non-negative capacities \(c(e)\) for all edges \(e \in E\). Furthermore, let \(s \in V\) be the selected source and \(t \in V\) the selected target.

Together, they build a network \(N = (G,c,s,t)\).

The goal is then to find flow values \(f(e)\) for all edges \(e \in \E\) respecting the given capacities \(c\), so that the total flow f * its maximum value reaches.

Here, f * is referred to the flow, going from the source \(s\) to the target \(t\). This means: the sum over all flow values from all edges leaving the node \(s\), which is equals the sum over all flow values from all edges arriving at the node \(t\).


Click on next to start the algorithm

Initializing the flow

Select the so called zero-flow as the starting flow. This means setiing \(f(e) = 0\) for all edges \(e \in E\) in the graph \(G\).

The starting flow will be increased during the algorithm until the maximum flow has been found.



Annotation:Every valid flow can be chosen as the starting flow. It does not have to be the zero-flow. It is only important that the capacity values remain respected. Nevertheless, the zero-flow is a good choice for the starting flow, because it always respects the given non-negative capacities.

Entering the main loop

The main loop is runned repeatedly, until no path from the source \(s\) to the target \(t\) can be found on the residual network \(N_f\).

Such a path on \(N_f\) is called augmenting path. The total flow is increased along this path.

The residual network, which will be constructed in the next step, gives for all edges the information by how much the flow may be increased or reduced. This make the new edges for the residual and backward capacities possible.


Click now on next step in order to find our more about \(N_f\).


Do you want to try it?

Apply the augmenting path

Increase the total flow f * by the augmenting value \(a\).

Increase the flow along the augmenting path as follows:

Apply \(f(e) = f(e) + a\), if the forward edge \(e'\) of \(e\) is on the path and

\(f(e) = f(e) - a\), if the backward edge \(e''\) of \(e\) is on the path.


How can be an augmenting path be found?

Finished

No other (\(s,t\))-path found on the residual network.

The algorithm terminated with a maximum flow value f * of:


Annotation: The algorithm always gives a maximum flow as output if it terminates. Furthermore, it always terminates after a finite number of iterations if the given capacities are non-negative integer numbers.

More details about the algorithm?

s ← select(v)

t ← select(v)

BEGIN

INPUT: network N = (G,c,s,t)

with G = (V,E), s,t ∈ V

OUTPUT: flow values f(e) for all e ∈ E,

maximum flow f*

(* Initialize the flow *)

FOR { e ∈ E } DO

f(e) ← 0

(* Main Loop *)

WHILE (s,t)-path on res.network found DO

f* ← f* + augmentation

FOR {e ∈ path}

flow(e) ← flow(e) + augmentation

RETURN f, f*

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.

SVG Download

Legende

node Node
node S/T Node
edge Edge with capacity 10 and flow 7.
edge Edge on residual network.
edge Edge on residual network.

Legende

Test your knowledge: answer the questions!

Is the flow already a maximum flow?

What ist the augmentation value?

Which are the capacity values on the residual network?

-You have the chance to answer these and more questions by running the algorithm!


Choose a network for this exercise!

Click on next step to start with the exercise

First choose a source node

Click on a node to select it as the source \(s\).

Then choose a target node

Click on a node to select it as the target or sink \(t\).

Ford-Fulkerson: a maximum flow algorithm

Let now \(G = (V,E)\) be the created graph with the respective non-negative capacities \(c(e)\) for all edges \(e \in E\). Furthermore, let \(s \in V\) be the selected source and \(t \in V\) the selected target.

Together, they build a network \(N = (G,c,s,t)\).

The goal is then to find flow values \(f(e)\) for all edges \(e \in E\) respecting the given capacities \(c\), so that the total flow f * its maximum value reaches.


Answer the multiple choice questions during the algorithm!

Click on next to start!

Initializing the flow

Select the so called zero-flow as the starting flow. This means setiing \(f(e) = 0\) for all edges \(e \in E\) in the graph \(G\).

The starting flow will be increased during the algorithm until the maximum flow has been found.

Entering the main loop

The main loop is runned repeatedly, until no path from the source \(s\) to the target \(t\) can be found on the residual network \(N_f\).

Apply the augmenting path

Increase the total flow f * by the augmenting value \(a\).

Increase the flow along the augmenting path.

Finished

No other (\(s,t\))-path found on the residual network.

The algorithm terminated with a maximum flow value f * of:

Do you want to keep practicing?

s ← choose(v)

t ← choose(v)

BEGIN

INPUT: Network N = (G,c,s,t)

OUTPUT:Flow f(e) for all e ∈ E,

maximum flow value f*

(* Initialize the flow *)

FOR { e ∈ E } DO

f(e) ← 0

(* Main loop *)

WHILE ex. (s,t)-path on res.network DO

f* ← f* + Aug

FOR {e ∈ path}

f(e) ← f(e) + Aug

RETURN f, f*

END

Here you can test your knowledge

The algorithm runs once again and stops at some points so that questions can be asked.

Tip: Read the description of the algorithm.

Good luck!

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.

SVG Download

Legende

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

Legende

Build the residual network!

Complete the capacities on the residual network

You will receive different networks \(N\) with capacities \(c(e)\) and flow values \(f(e)\) for all edges \(e \in E\), based on a current flow \(f\).

Your task is to complete the residual capacities \(c(e')\) and \(c(e'')\) of the residual edges \(e'\) and \(e''\) on the residual network N f .


Choose a number of networks for this exercise:


Here you can try building residual networks!

Complete the missing residual capacities on the residual network!

WARNING:You are only allowed to fill a capacity value once!

Tip: Read the description of residual networks.

Good luck!

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.