Max Flow

In this applet we realize Ford and Fulkerson's Max Flow algorithm.

The Max Flow problem consist of a directed graph, edges are labeled with capacities, and there are two distinct nodes: the source (pink) and the sink (orange). A flow is an assignment of flows to each each, such that

The aim is to find a flow which maximizes the incoming flow at the sink.

Ford and Fulkerson's algorithm

Ford and Fulkerson's algorithm is very old, but very simple. It starts with the null-flow and repeats the following stage until the Max Flow is reached: In the stage the algorithm tries to find a path from the source to the sink, such that the flow in the corresponding edges, can be augmented. This is called an augmenting path. (Drawn in red in the applet below).

The button run executes once this stage.

This applet is made by Ninh Lê Ðúc and Christoph Dürr.