Scribd
Upload
152 views11 pages

Edmond-Karp Algorithm

The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method that uses BFS to find augmenting paths for maximum flow, with a time complexity of O(V E^2). It involves initializing the flow network, finding augmenting paths, calculating bottleneck capacities, and augmenting flow until no more paths exist. Applications include maximizing flow in transportation and computer networks.

Uploaded by

vinusrinivasr2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
152 views11 pages

Edmond-Karp Algorithm

The Edmonds-Karp algorithm is an implementation of the Ford-Fulkerson method that uses BFS to find augmenting paths for maximum flow, with a time complexity of O(V E^2). It involves initializing the flow network, finding augmenting paths, calculating bottleneck capacities, and augmenting flow until no more paths exist. Applications include maximizing flow in transportation and computer networks.

Uploaded by

vinusrinivasr2006
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

NETWORK FLOWS

MODULE-4
Edmonds Karp Algorithm for maximum flow
• Edmonds-Karp algorithm is just an implementation of the Ford-
Fulkerson method that uses BFS for finding augmenting paths.
• The algorithm was first published by Yefim Dinitz in 1970, and
later independently published by Jack Edmonds and Richard Karp
in 1972.
• The complexity can be given independently of the maximal flow.
The algorithm runs in O(V E^2) time, even for irrational
capacities.
• The intuition is, that every time we find an augmenting path one of
the edges becomes saturated, and the distance from the edge to s
will be longer if it appears later again in an augmenting path. The
length of the simple paths is bounded by V.
Max flow=21
Practice
Solution:
Algorithm:
1. Initialize the flow network with zero flow.
2. Repeat the following steps until there are no more augmenting
paths:
a. Use BFS to find an augmenting path from the source to the
sink with the smallest number of edges.
b. Calculate the bottleneck capacity of the augmenting path,
which is the minimum capacity of all the edges in the path.
c. Augment the flow along the augmenting path by the
bottleneck capacity.
3. The maximum flow is the sum of all the flow values leaving the
source.
Note:
• The bottleneck capacity of an augmenting path is the limiting factor
for how much flow can be sent along that path.
• The algorithm repeatedly finds augmenting paths and sends as much
flow as possible along them until no more such paths exist.
Augmenting path :
1)Non-full forward edges
2)Non-empty backward edges(non-zero)
Complexity
The complexity of Edmonds Karp is
Worst case time complexity: Θ(V * E * E)
Space complexity: Θ(E + V)
Applications

• Finding the maximum flow in a flow network.


• Maximizing the transportation with given traffic limits.
• Maximizing packet flow in computer networks.

You might also like