Max flow and min cut are fundamental concepts in network flow theory. They are used to model and analyze the maximum amount of flow that can be sent through a network, as well as the minimum capacity needed to disconnect certain parts of the network. The Ford-Fulkerson algorithm is an algorithm used to find the maximum flow in a network.
A network flow is a directed graph where each edge has a capacity representing the maximum amount of flow that can be sent through it. It consists of a source node, a sink node, and intermediate nodes connected by edges with capacities. The goal is to find the maximum amount of flow that can be sent from the source to the sink while respecting the capacity constraints.
The Ford-Fulkerson algorithm is an iterative algorithm that finds the maximum flow in a network. It starts with an initial flow of zero and repeatedly augments the flow along the augmenting paths until no more augmenting paths exist. An augmenting path is a path from the source to the sink where each edge has residual capacity (capacity minus current flow) greater than zero.
The algorithm finds an augmenting path using a graph traversal technique such as depth-first search (DFS) or breadth-first search (BFS). Once an augmenting path is found, the algorithm determines the maximum amount of flow that can be sent along the path and updates the flow values accordingly.
function FordFulkerson(graph, source, sink):
residualGraph := createResidualGraph(graph)
flow := 0
while there is an augmenting path in residualGraph:
augmentingPath := findAugmentingPath(residualGraph, source, sink)
bottleneck := findBottleneckCapacity(augmentingPath)
updateFlow(residualGraph, augmentingPath, bottleneck)
flow := flow + bottleneck
return flow