FordFulkersonEdmondsKarp

The Ford-Fulkerson algorithm is a method for computing the maximum flow in a flow network. A flow network is a directed graph where each edge has a capacity, and there is a designated source node and a sink node. The goal is to find the maximum amount of "flow" that can be sent from the source to the sink without exceeding the capacity of any edge.

The algorithm works by repeatedly finding an augmenting path from the source to the sink in the residual graph. An augmenting path is a path along which flow can be increased. The residual graph represents the remaining capacity on each edge. If an edge has a capacity of c and currently carries flow f, its residual capacity is c - f. Additionally, for every edge with flow f, a backward edge is created in the residual graph with capacity f, allowing flow to be "pushed back" if necessary.

Once an augmenting path is found, the algorithm determines the bottleneck capacity of that path, which is the minimum residual capacity of any edge along the path. This bottleneck capacity is then added to the total flow, and the residual capacities of the edges along the path are updated. Edges in the direction of the augmenting path have their residual capacity decreased, while backward edges have their residual capacity increased.

This process continues until no more augmenting paths can be found from the source to the sink in the residual graph. At this point, the total flow accumulated is the maximum possible flow for the given network. The Ford-Fulkerson algorithm is guaranteed to terminate and find the maximum flow if all capacities are integers. For networks with non-integer capacities, it might not terminate. The efficiency of the algorithm depends on how augmenting paths are chosen. Specific implementations like Edmonds-Karp use Breadth-First Search (BFS) to find the shortest augmenting path in terms of the number of edges, which leads to a polynomial time complexity.