[go: up one dir, main page]
Scribd
Upload
46 views6 pages

Ford-Fulkerson Algorithm

Uploaded by

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

Ford-Fulkerson Algorithm

Uploaded by

Surya kumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 6

Ford-Fulkerson Algorithm

Ford-Fulkerson algorithm is a greedy approach for calculating the maximum possible flow in
a network or a graph.
A term, flow network, is used to describe a network of vertices and edges with a source (S)
and a sink (T). Each vertex, except S and T, can receive and send an equal amount of stuff
through it. S can only send and T can only receive stuff.
We can visualize the understanding of the algorithm using a flow of liquid inside a network of
pipes of different capacities. Each pipe has a certain capacity of liquid it can transfer at an
instance. For this algorithm, we are going to find how much liquid can be flowed from the
source to the sink at an instance using the network.
Terminologies Used

Augmenting Path
It is the path available in a flow network.
• Non-Full Forward Edges
• Non-Empty (Non-Zero) backward Edges

Minimal Cut – Bottle neck capacity


It describe the maximum possible flow from source
to sink through an augmented path.

Residual Capacity
It is the capacity of the edge after subtracting the
flow from the maximum capacity.

Residual Graph
It represents the flow network that has additional
possible flow.
How Ford-Fulkerson Algorithm
works?
The algorithm follows:

1.Initialize the flow in all the edges to 0.


2.While there is an augmenting path between the source and the sink, add this path to
the flow.
3.Update the residual graph.

We can also consider reverse-path if required because if we do not consider them, we


may never find a maximum flow.
1] The flow of all the edges is 0 at the beginning. 3] The minimum capacity among the three edges is 2 (B-T).
Based on this, update the flow/capacity for each path.

2] Select any arbitrary path from S to T. In this step, we have 4] Select another path S-D-C-T. The minimum capacity among
selected path S-A-B-T these edges is 3 (S-D).
5] Update the capacities according to this. 7] Updating the capacities.

6] Now, let us consider the reverse-path B-D as well. Selecting The capacity for forward and reverse paths are
path S-A-B-D-C-T. The minimum residual capacity among the considered separately.
edges is 1 (D-C).
Adding all the flows = 2 + 3 + 1 = 6, which is the
maximum possible flow on the flow network.

Note that if the capacity for any edge is full, then


that path cannot be used.
Maxflow = 5+2+2+1 = 10

You might also like