Max-Flow / Min-Cut: Ford–Fulkerson Algorithm in 2D |…

What is Max-Flow / Min-Cut?

Max-Flow/Min-Cut problems deal with determining the largest possible flow that can be sent from a source to a sink in a network, where each edge has a capacity. The max-flow problem seeks to find an optimal flow assignment that maximizes the total amount of flow from the source to the sink without violating any edge capacities.

The min-cut is the set of edges whose removal disconnects the source from the sink and has the minimum possible capacity sum, which equals the maximum flow value. This duality between max-flow and min-cut is a cornerstone in network theory.

How Does Ford–Fulkerson Work?

The Ford-Fulkerson algorithm is an iterative method that finds augmenting paths from the source to the sink in the residual graph. An augmenting path is a path where we can push more flow, and the bottleneck capacity of such a path determines how much additional flow can be sent.

Each iteration increases the total flow until no more augmenting paths exist, at which point the maximum flow has been achieved, and the min-cut is revealed as the set of edges with full capacity in the residual graph.

live demo · related simulation● LIVE

Why Does It Matter?

Max-Flow/Min-Cut algorithms are crucial for optimizing resource allocation in various fields. For instance, they can be used to optimize data routing in computer networks, manage traffic flow in transportation systems, and allocate resources in supply chains.

Understanding these concepts is vital for designing efficient systems that handle large volumes of data or people, ensuring optimal performance and minimizing bottlenecks.

Real-World Examples

In telecommunications, max-flow algorithms help determine the maximum bandwidth available in a network by finding the path with the least capacity. This is essential for managing data traffic and ensuring reliable communication.

In urban planning, these principles can be applied to optimize traffic flow, reducing congestion and improving overall transportation efficiency.

Frequently asked questions

What does an augmenting path mean in the context of max-flow?

An augmenting path is a path from the source to the sink in the residual graph where we can push more flow. The capacity of this path determines how much additional flow can be sent.

How does the Ford-Fulkerson algorithm ensure that it finds the maximum possible flow?

The algorithm iteratively finds augmenting paths and increases the flow along these paths until no more such paths exist. At this point, the current flow is guaranteed to be the maximum possible.

What is a residual graph in max-flow problems?

A residual graph represents the remaining capacity for sending flow from one node to another after some flow has already been sent. It includes both forward and backward edges, allowing us to find augmenting paths more efficiently.

Why is understanding the min-cut important in max-flow problems?

The min-cut represents the smallest set of edges that, if removed, would disconnect the source from the sink. Its capacity equals the maximum flow value, providing a clear indication of the network's bottleneck and helping to identify critical components.

Try it live

Everything above runs in your browser — open Max-Flow / Min-Cut — Ford–Fulkerson (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Max-Flow / Min-Cut — Ford–Fulkerson (2D) simulation