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

Edmonds-Karp Algorithm

The Edmonds-Karp Algorithm is a maximum flow algorithm that uses breadth-first search to find the shortest augmenting path in the residual network. This path-selection rule provides a polynomial-time running-time guarantee.

Explanation

Overview

Edmonds-Karp is an implementation of the Ford-Fulkerson method that always chooses an augmenting path with the fewest edges, using breadth-first search (BFS). After finding the path, it sends as much additional flow as possible along it, updates the residual capacities, and repeats until no augmenting path remains.

Key concepts

name: Core idea; description: The central focus of edmonds-karp algorithm is the capability described here: The Edmonds-Karp Algorithm is a maximum flow algorithm that uses breadth-first search to find the shortest augmenting path in the residual network. This path-selection rule provides a polynomial-time running-time guarantee.; name: Problem context; description: Edmonds-Karp Algorithm is relevant when a computational task requires the behavior or capability described by this topic.; name: Correct use; description: Before using edmonds-karp algorithm, check its assumptions, input requirements, expected output, and resource constraints.

Complexity

time: O(V × E²).; space: O(V + E) for an adjacency-list residual graph.; explanation: BFS takes O(V + E) time. The key theoretical result is that the number of augmentations is bounded by O(V × E), leading to the O(V × E²) total bound.

Example

scenario: A network contains several possible routes from a source to a sink.; description: BFS explores vertices level by level and chooses a route containing the fewest edges among the available augmenting paths.; illustration: If one available route contains two edges and another contains four edges, BFS chooses the two-edge route, provided both are valid in the residual network.; explanation: After the chosen path is augmented, the residual graph changes and BFS is run again.

Pseudocode

EDMONDS-KARP(G, s, t):
initialize all flows to 0
totalFlow = 0
while BFS finds a path P from s to t in the residual graph:
bottleneck = minimum residual capacity on P
update residual capacities along P
totalFlow = totalFlow + bottleneck
return totalFlow

Applications

Network flow optimization.; Bipartite matching.; Transportation and logistics.; Communication networks.; Resource allocation and scheduling.

Advantages

Provides a guaranteed polynomial-time running-time bound.; Uses a familiar BFS procedure.; Avoids the unpredictable path-selection behavior of arbitrary Ford-Fulkerson implementations.; Works with general nonnegative capacities.

Example or application

Scenario

A network contains several possible routes from a source to a sink.

Description

BFS explores vertices level by level and chooses a route containing the fewest edges among the available augmenting paths.

Illustration

If one available route contains two edges and another contains four edges, BFS chooses the two-edge route, provided both are valid in the residual network.

Explanation

After the chosen path is augmented, the residual graph changes and BFS is run again.

Definition

Edmonds-Karp is an implementation of the Ford-Fulkerson method that always chooses an augmenting path with the fewest edges, using breadth-first search (BFS). After finding the path, it sends as much additional flow as possible along it, updates the residual capacities, and repeats until no augmenting path remains.

Relationship To Ford Fulkerson

Ford-Fulkerson describes the general augmenting-path method and does not prescribe one particular path-search strategy. Edmonds-Karp specifies BFS, which ensures that augmenting paths are selected in nondecreasing order of edge distance from the source.

Algorithm Steps

  • Initialize the flow to zero.

  • Build or maintain the residual network.

  • Run BFS from the source to find a path to the sink.

  • If the sink cannot be reached, return the current maximum flow.

  • Determine the minimum residual capacity along the discovered path.

  • Update the forward and reverse residual capacities.

  • Add the bottleneck amount to the total flow.

  • Repeat the BFS process.

Pseudocode

EDMONDS-KARP(G, s, t):
initialize all flows to 0
totalFlow = 0
while BFS finds a path P from s to t in the residual graph:
bottleneck = minimum residual capacity on P
update residual capacities along P
totalFlow = totalFlow + bottleneck
return totalFlow

Complexity

Time

O(V × E²).

Space

O(V + E) for an adjacency-list residual graph.

Explanation

BFS takes O(V + E) time. The key theoretical result is that the number of augmentations is bounded by O(V × E), leading to the O(V × E²) total bound.

Advantages

  • Provides a guaranteed polynomial-time running-time bound.

  • Uses a familiar BFS procedure.

  • Avoids the unpredictable path-selection behavior of arbitrary Ford-Fulkerson implementations.

  • Works with general nonnegative capacities.

Limitations

  • Can be slower than more advanced maximum flow algorithms on some large or dense networks.

  • Repeated BFS searches can be expensive when the graph contains many edges.

  • Maintaining reverse residual edges and correct capacity updates requires careful implementation.

Implementation Considerations

  • Use a queue for BFS.

  • Store parent information to reconstruct the augmenting path.

  • Treat only edges with positive residual capacity as available.

  • Update both forward and reverse residual capacities after each augmentation.

  • Use a numeric type that can represent the total capacity without overflow.

Applications

  • Network flow optimization.

  • Bipartite matching.

  • Transportation and logistics.

  • Communication networks.

  • Resource allocation and scheduling.

Related Topics

  • INFO-CS-ADS-238

  • INFO-CS-ADS-239

  • INFO-CS-ADS-241

  • INFO-CS-ADS-242

Practice Questions

QuestionAnswer

Which search algorithm does Edmonds-Karp use?

Breadth-first search (BFS).

How does Edmonds-Karp choose an augmenting path?

It chooses a path with the fewest edges in the residual network.

What is its time complexity?

O(V × E²).

How does Edmonds-Karp differ from general Ford-Fulkerson?

It specifically uses BFS to select augmenting paths, giving a polynomial-time guarantee.

Key Concepts

NameDescription

Core idea

The central focus of edmonds-karp algorithm is the capability described here: The Edmonds-Karp Algorithm is a maximum flow algorithm that uses breadth-first search to find the shortest augmenting path in the residual network. This path-selection rule provides a polynomial-time running-time guarantee.

Problem context

Edmonds-Karp Algorithm is relevant when a computational task requires the behavior or capability described by this topic.

Correct use

Before using edmonds-karp algorithm, check its assumptions, input requirements, expected output, and resource constraints.

Learning Objectives

  • Explain the central idea and purpose of edmonds-karp algorithm.

  • Identify the assumptions, inputs, and conditions relevant to edmonds-karp algorithm.

  • Evaluate an application of edmonds-karp 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