✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-239

Ford-Fulkerson Algorithm

The Ford-Fulkerson Algorithm solves maximum flow problems by repeatedly finding augmenting paths in a residual network and increasing the flow along those paths until no augmenting path remains.

Explanation

Overview

Ford-Fulkerson is a general method for computing a maximum flow in a capacitated directed network. It begins with zero flow and repeatedly searches for a path from the source to the sink in the residual graph. The algorithm sends additional flow along the path, limited by the smallest residual capacity on that path. It stops when no augmenting path exists.

Key concepts

name: Augmenting Path; description: A source-to-sink path in the residual network along which additional flow can be sent.; name: Bottleneck Capacity; description: The smallest residual capacity among the edges of an augmenting path. It determines the maximum amount that can be added along that path.; name: Residual Graph; description: A graph representing remaining forward capacity and the ability to cancel previously sent flow through reverse edges.; name: Reverse Edge; description: An edge in the residual network that allows some previously assigned flow to be canceled or rerouted.

Complexity

integerCapacities: O(E × F) for a standard augmenting-path implementation, where E is the number of edges and F is the maximum flow value.; space: O(V + E) for a typical adjacency-list residual network.; importantNote: The running time depends on the method used to find augmenting paths. With arbitrary real capacities, a poor path-selection strategy can fail to terminate in certain cases.

Example

scenario: A network has a source S, intermediate vertices A and B, and a sink T.; description: The algorithm finds a valid path from S to T, identifies the smallest remaining capacity on that path, and sends that amount of flow.; illustration: If a path has residual capacities 8, 5, and 7, its bottleneck capacity is 5. The algorithm can augment the flow along that path by 5 units.; nextStep: The residual network is updated, and another augmenting path may become available.

Pseudocode

FORD-FULKERSON(G, s, t):
initialize flow to 0 on every edge
while an augmenting path P exists from s to t in the residual graph:
bottleneck = minimum residual capacity on P
for each edge (u, v) in P:
update flow using bottleneck
update forward and reverse residual capacities
return total flow leaving s

Applications

Transportation network analysis.; Resource distribution.; Communication network capacity analysis.; Matching and assignment problems.; Supply chain planning.

Advantages

Conceptually simple and based on repeated path searches.; Works with a wide range of network structures.; Provides a foundation for understanding maximum flow algorithms.; Can be effective for small networks and suitable capacity values.

Example or application

Scenario

A network has a source S, intermediate vertices A and B, and a sink T.

Description

The algorithm finds a valid path from S to T, identifies the smallest remaining capacity on that path, and sends that amount of flow.

Illustration

If a path has residual capacities 8, 5, and 7, its bottleneck capacity is 5. The algorithm can augment the flow along that path by 5 units.

Next Step

The residual network is updated, and another augmenting path may become available.

Definition

Ford-Fulkerson is a general method for computing a maximum flow in a capacitated directed network. It begins with zero flow and repeatedly searches for a path from the source to the sink in the residual graph. The algorithm sends additional flow along the path, limited by the smallest residual capacity on that path. It stops when no augmenting path exists.

Key Concepts

NameDescription

Augmenting Path

A source-to-sink path in the residual network along which additional flow can be sent.

Bottleneck Capacity

The smallest residual capacity among the edges of an augmenting path. It determines the maximum amount that can be added along that path.

Residual Graph

A graph representing remaining forward capacity and the ability to cancel previously sent flow through reverse edges.

Reverse Edge

An edge in the residual network that allows some previously assigned flow to be canceled or rerouted.

Algorithm Steps

  • Initialize the flow on every edge to zero.

  • Construct the residual network from the original capacities and current flow.

  • Find an augmenting path from the source to the sink.

  • If no augmenting path exists, terminate.

  • Find the minimum residual capacity along the selected path.

  • Increase flow along forward edges and update reverse residual capacities.

  • Repeat until no additional source-to-sink path exists.

Pseudocode

FORD-FULKERSON(G, s, t):
initialize flow to 0 on every edge
while an augmenting path P exists from s to t in the residual graph:
bottleneck = minimum residual capacity on P
for each edge (u, v) in P:
update flow using bottleneck
update forward and reverse residual capacities
return total flow leaving s

Complexity

Integer Capacities

O(E × F) for a standard augmenting-path implementation, where E is the number of edges and F is the maximum flow value.

Space

O(V + E) for a typical adjacency-list residual network.

Important Note

The running time depends on the method used to find augmenting paths. With arbitrary real capacities, a poor path-selection strategy can fail to terminate in certain cases.

Why Reverse Edges Matter

  • An early path choice may prevent a later path from carrying more flow.

  • Reverse residual edges allow the algorithm to cancel part of an earlier flow assignment.

  • This makes it possible to reroute flow through a better combination of paths.

  • Ignoring reverse edges can lead to an incorrect result.

Advantages

  • Conceptually simple and based on repeated path searches.

  • Works with a wide range of network structures.

  • Provides a foundation for understanding maximum flow algorithms.

  • Can be effective for small networks and suitable capacity values.

Limitations

  • Its performance can depend heavily on augmenting-path selection.

  • The O(E × F) bound may be large when capacities or maximum flow values are large.

  • Arbitrary real capacities can create nontermination concerns for unsuitable path-selection strategies.

  • It may be less predictable than algorithms with a stronger polynomial-time bound.

Applications

  • Transportation network analysis.

  • Resource distribution.

  • Communication network capacity analysis.

  • Matching and assignment problems.

  • Supply chain planning.

Related Topics

  • INFO-CS-ADS-238

  • INFO-CS-ADS-240

  • INFO-CS-ADS-241

  • INFO-CS-ADS-242

Practice Questions

QuestionAnswer

What is an augmenting path?

A source-to-sink path in the residual graph that can carry additional flow.

How is the bottleneck capacity calculated?

It is the minimum residual capacity among the edges in the augmenting path.

Why does Ford-Fulkerson use reverse residual edges?

They allow earlier flow to be canceled or rerouted when a better overall flow is found.

What is a common integer-capacity running-time bound?

O(E × F), where F is the maximum flow value.

Learning Objectives

  • Explain the central idea and purpose of ford-fulkerson algorithm.

  • Identify the assumptions, inputs, and conditions relevant to ford-fulkerson algorithm.

  • Evaluate an application of ford-fulkerson algorithm for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Advanced Algorithm Theory and Applications

Suggest a correction or source · More in Algorithms & Data Structures