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 flow does not exceed the capacity for each edge,
- the sum of the incoming flows equals the sum of the outgoing flows
for each edge, but the source or the sink.
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.