Ford-Fulkerson Algorithm

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.

## Legende

 Node Edge with capacity 10

## Which graph do you want to execute the algorithm on?

### 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!

A occured when reading from file: the contents:

## Legende

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

## 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.

## Legende

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

## Which are the capacity values on the residual network?

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

### 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.

## Legende

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

## 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}$.

## 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.