Maximum Flow

The maximum flow problem is a fundamental problem in graph theory that seeks to find the maximum amount of flow that can be sent from a source node to a sink node in a network. It has applications in various fields, including transportation, telecommunications, and computer networks.

Problem Definition

Given a directed graph with a source node and a sink node , and a capacity function that assigns a non-negative capacity to each edge, the maximum flow problem seeks to find the maximum amount of flow that can be sent from to through the network.