Ford-Fulkerson Algorithm

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.

## 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.
• Right-clicking deletes edges and nodes.

Download

### Upload an existing graph:

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

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

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.