Algorithm Design | Network Flow | Ford-Fulkerson Algorithm | MAXIMAL FLOW PROBLEM | MAX FLOW PROBLEM

Summary

This educational video delves into the Max Flow problem using the Ford-Fulkerson algorithm, a crucial concept in network flow. The script begins by explaining fundamental terms like source, sink, capacity, and residual capacity, essential for understanding network flow applications, such as water supply systems. The instructor illustrates the importance of maximum flow in practical scenarios and then outlines the steps of the Ford-Fulkerson algorithm, including assigning initial flow, selecting augmenting paths, and updating flow until no more paths can be found. The video provides a step-by-step example to find the maximum flow in a given network, focusing on non-full forward edges, and concludes with a summary of the algorithm's process and its application in solving network flow problems.

Takeaways

• 📚 The video discusses the Max Flow problem using the Ford-Fulkerson algorithm, which is part of Network Flow.
• 🔍 Prerequisites for understanding Network Flow include terms like source, sink, capacity, residual capacity, and augmented path.
• 💧 An analogy for Network Flow is provided using water pipes in a home, emphasizing the importance of proper flow management.
• 🚀 The importance of Network Flow is highlighted with examples from computer networks and everyday scenarios like water supply.
• 🔑 Key terms are defined: 'source' has no incoming edges, 'sink' has no outgoing edges, and 'bottleneck' refers to the limiting factor in flow.
• 🔄 The Ford-Fulkerson algorithm involves assigning initial flow as zero, selecting augmenting paths, finding residual capacities, and updating the flow.
• 🔢 Residual capacity is calculated as the original capacity minus the flow, determining how much more flow can be sent through a path.
• 🔍 Augmenting paths are paths from source to sink with available capacity; they must be selected carefully to maximize flow.
• 🔁 The algorithm continues until no more augmenting paths can be found with a residual capacity greater than zero.
• 📈 The maximum flow is determined by summing the flows through all the augmenting paths identified during the algorithm.
• 🚫 The script specifies that backward edges are not considered in this particular example, focusing only on non-full forward edges.

Q & A

What is the main topic discussed in the video?

The main topic discussed in the video is the Max Flow problem using the Ford-Fulkerson algorithm.

What are the prerequisites for understanding the Network Flow?

The prerequisites for understanding Network Flow include terms such as source, sink, capacity, residual capacity, and augmented path.

Why is Network Flow important?

Network Flow is important because it is used in solving problems related to computer networks and can be likened to real-life scenarios such as water flow in a household system.

What does the term 'source' represent in Network Flow?

In Network Flow, the 'source' represents the starting point of the flow, similar to a water tank where water is stored and has no incoming edges.

What is meant by 'sink' in the context of Network Flow?

A 'sink' in Network Flow is the endpoint or destination where the flow terminates, having no outgoing edges.

Can you explain the concept of 'bottleneck capacity' in the video?

The 'bottleneck capacity' refers to the maximum flow that can pass through a particular path, similar to the narrow neck of a water bottle that restricts the flow.

What is an 'augmented path' in the Ford-Fulkerson algorithm?

An 'augmented path' in the Ford-Fulkerson algorithm is a path from the source to the sink in the residual graph that has a residual capacity greater than zero, allowing for an increase in the total flow.

How does the Ford-Fulkerson algorithm find the maximum flow?

The Ford-Fulkerson algorithm finds the maximum flow by iteratively finding augmenting paths in the residual graph and updating the flow along these paths until no more augmenting paths can be found.

What does 'residual capacity' mean in the context of the Ford-Fulkerson algorithm?

In the Ford-Fulkerson algorithm, 'residual capacity' refers to the remaining capacity of an edge after accounting for the current flow, which can be used to increase the flow from the source to the sink.

How is the initial flow assigned in the Ford-Fulkerson algorithm?

In the Ford-Fulkerson algorithm, the initial flow is assigned as zero for all paths in the network.

What is the significance of finding the minimum residual capacity in the algorithm?

The significance of finding the minimum residual capacity in the algorithm is to determine the amount by which the flow can be increased along the augmenting path, as it represents the bottleneck for that path.

How does the video script illustrate the concept of network flow?

The video script illustrates the concept of network flow by using the analogy of water flow in a household system, where the water tank is the source, the taps are the sinks, and the pipes represent the paths with their capacities.

Outlines

00:00

📚 Introduction to Network Flow and Ford-Fulkerson Algorithm

This paragraph introduces the concept of network flow, which is essential for solving traffic problems in computer networks, using a relatable example of water flow in a home's plumbing system. The speaker explains the importance of proper flow and introduces key terms such as 'source', 'sink', 'capacity', 'residual capacity', and 'augmented path'. The paragraph sets the stage for a detailed discussion on the Ford-Fulkerson algorithm for finding the maximum flow in a network.

05:01

🔍 Understanding Prerequisites for Network Flow

The speaker delves deeper into the prerequisites for network flow, emphasizing the significance of understanding terms like 'bottleneck capacity' and 'residual capacity'. The explanation of 'residual capacity' is illustrated with the analogy of a water bottle, where the narrow neck represents the limiting factor in flow. The paragraph also introduces the concept of an 'augmenting path', which is crucial for the Ford-Fulkerson algorithm, and distinguishes between two types: those with only forward edges and those with a combination of forward and backward edges.

10:02

🛠 Steps of the Ford-Fulkerson Algorithm

This paragraph outlines the steps involved in the Ford-Fulkerson algorithm. It begins with assigning an initial flow of zero to all paths in the network. The speaker then explains the process of selecting an augmenting path from the source to the sink, calculating the residual capacity of this path, and updating the flow. The algorithm continues this process, finding new augmenting paths and updating flows until no more can be found, indicating that the maximum flow has been reached.

15:05

🔄 Application of Ford-Fulkerson Algorithm to a Sample Problem

The speaker applies the Ford-Fulkerson algorithm to a sample problem, explaining how to assign initial flows, select augmenting paths, and calculate residual capacities. The paragraph provides a step-by-step guide on how to update the flow through the network based on the minimum residual capacity found in an augmenting path. It also discusses the concept of non-conflict paths and how to manage the flow to ensure that the network operates efficiently.

20:07

📉 Continuing the Ford-Fulkerson Algorithm with Residual Capacities

This paragraph continues the application of the Ford-Fulkerson algorithm, focusing on the importance of residual capacities in finding new augmenting paths. The speaker demonstrates how to calculate and compare residual capacities to select the path that will contribute to the maximum flow. The explanation includes updating the flow through the network and marking paths that can no longer be used when their residual capacity reaches zero.

25:10

🏁 Conclusion and Final Calculation of Maximum Flow

In the final paragraph, the speaker concludes the Ford-Fulkerson algorithm by summing up the residual capacities collected throughout the process to determine the maximum flow. The paragraph emphasizes the importance of following the algorithm's steps carefully to ensure accurate results. The speaker also hints at the next topic to be covered in the series, which involves mean cut and its relation to maximum flow.

Keywords

💡Network Flow

Network Flow is a concept that models the movement of resources through a network, such as water through pipes or data through computer networks. In the context of the video, it is the main theme and refers to the process of finding the maximum amount of flow from a source to a sink in a network while adhering to the capacities of the edges. The script uses the analogy of water flow in a home to explain the concept, emphasizing the importance of proper flow management.

💡Ford-Fulkerson Algorithm

The Ford-Fulkerson Algorithm is a method used to compute the maximum flow in a flow network. It works by finding augmenting paths in the residual graph and augmenting the flow along these paths until no more augmenting paths can be found. The video script discusses this algorithm in detail, explaining its steps and how it is applied to solve network flow problems.

💡Source

In network flow, the Source is the starting point of the flow, where resources originate. The script mentions the Source (represented as 's') as the point from which the flow begins, using the water tank analogy to illustrate that water is stored in the tank and flows out through pipes to various destinations.

💡Sink

The Sink, also referred to as the destination, is the endpoint of the flow in a network. It is where the flow terminates, and no outgoing edges are present from the Sink. The script uses the Sink (represented as 't') to illustrate the end of the flow path, like a tap where water is used.

💡Capacity

Capacity in the context of network flow refers to the maximum amount of flow that a particular edge or pipe can handle. The script explains capacity by comparing it to the size of a water bottle's neck, which limits the rate at which water can be consumed, thereby setting a limit on the flow.

💡Residual Capacity

Residual Capacity is the remaining capacity of an edge after accounting for the current flow. It is used to determine how much more flow can be sent through a particular path. The script discusses how residual capacity is calculated by subtracting the flow from the original capacity and emphasizes its importance in the Ford-Fulkerson Algorithm.

💡Augmenting Path

An Augmenting Path is a path from the Source to the Sink in the residual graph that has a positive residual capacity. The Ford-Fulkerson Algorithm uses these paths to increase the total flow. The script explains that finding an augmenting path is a key step in the algorithm, and it uses the term 'augmented' to refer to a path that has been used to increase flow.

💡Flow

Flow represents the movement of resources through the network. In the script, flow is initially set to zero and is incrementally increased by finding augmenting paths. The video uses the term to describe the amount of resource (like water or data) that is being transferred through the network.

💡Prerequisites

The term Prerequisites in the script refers to the fundamental concepts or terms that must be understood before delving into the details of the Ford-Fulkerson Algorithm. These include understanding the Source, Sink, capacity, residual capacity, and augmenting path, which are essential for grasping how the algorithm works.

💡Non-full Forward Edges

Non-full Forward Edges are edges in the residual graph that have a positive residual capacity and can therefore be used to increase the flow. The script specifies that the algorithm will consider non-full forward edges, meaning edges that still have capacity available for additional flow, when searching for augmenting paths.

Highlights

Introduction to the Max Flow problem using Ford-Fulkerson algorithm.

Explanation of prerequisites for Network Flow, including terms like source, sink, capacity, residual capacity, and augmented path.

Importance of Network Flow in traffic solving problems and computer networks, with a practical example of water flow in a home.

Definition of source and sink in the context of Network Flow.

Concept of bottleneck capacity and its comparison to the size of a water bottle's neck.

Explanation of residual capacity as original capacity minus the current flow.

Discussion on augmenting paths, including non-full forward edges and the importance of selecting the minimum residual capacity.

Step-by-step guide on how to implement the Ford-Fulkerson algorithm, starting with assigning an initial flow of zero.

Selection of an augmenting path and the process of finding the residual capacity to update the flow.

Strategy for stopping the algorithm when the residual capacity of a path becomes zero, indicating no further flow is possible.

Example problem demonstration of finding the maximum flow in a given network using Ford-Fulkerson algorithm.

Process of updating the flow through each edge in the network based on the selected residual capacity.

Illustration of how to handle multiple paths and the selection of paths with non-conflicting minimum residual capacities.

Final calculation of the maximum flow by summing up all the residual capacities collected during the algorithm's execution.

Conclusion and summary of the Ford-Fulkerson algorithm's steps and its application in finding the max flow.

Preview of the next topic, mean cut, and its relation to max flow.

Transcripts

hello students welcome to ucil in this

video we are going to discuss about Max

flow problem using Ford Focus and

algorithm it's a part of our Network

flow before going in detail about the

algorithm we should know the

prerequisites of network flow here in

this network flow uh we have certain

prerequisites or you can say terms to be

known named our sorts syn buttoning

capacity residual capacity augmented

path these are certain terms which we

will be using throughout while solving

the

problem uh before going in detail about

the algorithm one more thing we should

know why netf flow is important for this

algorithm and what is this basically so

Network flow uh in general term I must

say we have used in our traffic solving

problems in uh computer networks or else

you can say a simple example nowadays we

are providing is like uh we are having

uh water tabs in our home okay so where

we're staying that we are having the

tabs and the problem is like it's stored

like the water tank is there on the top

of it there are definitely so many pipes

are getting connected but whenever we

need it the flow should be a proper flow

we should uh be uh you know really

interested for like the profer flow in

the sense like if you going for a PA so

in that sense what exactly does like uh

if the flow of the water okay if you're

using sour there suppose uh if your flow

is not that much adequate or might be

that it's not a proper flow which you

are expecting it's not a proper flow uh

there while you using sink or might be

you can say s suppose you are going to

take it and it's not a proper flow that

time what happen like the definitely the

tank is on the the above of it above of

any roof so what it does like there are

many connections okay from uh the tank

to the uh tab okay so tank is the source

there and you have the tab with you

which is a syn let us take an example of

syn why I'm using these terms because

these terms are going to be used in this

network flow so the flow should be

proper that's why we are reading it as

maximum flow means we may say it's a

flow but maximum means as for our

requirement we are getting it that's why

we are saying it's a Max flow okay

insert we are saying it's Max flow but

uh if I'll say it's a maximum flow also

it's correct okay so sorts is something

where uh we do not have any inward edges

only outward edges would be there like

IND degree is zero means not towards

anything like you know if I told you

like you just think the example of the

water tank water tank we will store the

water there there is no other path to be

connected only one path might be you can

consider those a practical problem

definitely we are storing the water

there that's why we need one pipe or two

pipes Max to Max but from there whenever

we are expecting the water should be

utilized by us that time we shouldn't

take any other path because we are

storing the water there so here also we

are thinking the sours okay next sink

you can say destination also as a part

of syn where out degree is zero means no

such out degree will expect there only

this is the end point okay next bottling

capacity and residual capacity which is

much needed to understand it well why

because bottling

capacity uh you just think like we have

a water bottle so water bottle

definitely the mouth of the ble could be

smaller why because we need a flow might

be you can think it's a Max flow but

whenever we are taking that one so the

bottle or the neck of the bottle should

be slow or the narrow as compared to the

body of the bottle or might be sometimes

you have seen like the still for all the

cases like the the opening mouth with

the body is also same not an issue but

we are talking about those bottles who

having the neck is small in size why

because it's easy for us to intake it

well okay so that is why we are focusing

on the capacity though we are focusing

on the pipes based on the pipes like the

capacity is good so definitely the flow

is also we will expect in a good way

sometimes the pipes are bigger sometimes

the pipes are also smaller okay so that

is what exactly the buttling capacity is

if any uh you know there is a path like

we can have source to might be there are

many distances if you have syn syn is

represented as T in our book okay source

is represented as s this is not always

correct but SD we are representing as

for the book in future there are certain

uh contents you can expect like SD Cod

there are many Concepts out there that's

why I'm representing it from s to D okay

next residual capacity residual capacity

some capacity you can say like we have

certain original capacity of the of like

whenever we'll go in detail that could

be very much easy for us to understand

before that we just discussing about

what are the prerequisites to be know

okay like residual capacity which is

like original capacity with the current

flow whenever we are writing it so the

flow should be written in this order

this way flow will be in the right left

hand side and the right hand side will

be the capacity capacity or you can say

it's the original capacity original

capacity original capacity of what like

the path or the pipe you can say Okay

flow this side original capacity will be

the right hand side next augmenting path

or augmented path once we have done the

proper flow we can say it's augmented

path as for the English okay but

whenever we are not doing it or mightbe

we are in a processing we can say it's

augmenting path there are two types of

augmenting path one is nonone full

forward edges you can say there is only

forward edges okay from

s2t uh

s2t next nonempty backward like you can

expect the backward from any point

suppose this is R from R you can expect

some back Wes there are also

combinations of this also possible but

right now in our example we'll be

focusing on non full forward ages okay

let us start with the for Fulon

algorithm here the solution steps I have

written for you as for the solution step

first we will understand how it is

running once it is done then we'll be

focusing on our one of the problems once

it is easy for you to understand then we

can say all over the IDE idea like which

we are targeting to read it using the

for focus and algorithm finding the max

flow that's could be easy for us once we

complete this algorithm steps uh with

the implementation of it okay so step

one assign initial flow of zero whenever

we have uh like question I'll be having

the next slide I'll show that one but

still the steps we should know first

what it represents like assign all the

initial flow as zero next is select any

augment path you can say it's augmenting

sometimes also you can see it like

augmenting and augmenting the main

reason actually why I'm using this as

augmented once uh the path we have

selected once we have the residual

capacity of any once you have selecting

any path like from source to destination

so that path is considered as augmented

path this path should be having the

connection from source to destination is

called as augmented path otherwise we

cannot say any path as augmented path if

the path is considering source to

destination only so this is what it is

representing okay source to sync okay so

once the path connected the connected

paths are from source to sync we have

then we say it's augmented path if we

doing work on this so we can say it's

augmenting path once it is done we say

it augmented path okay so find the

residual capacity and upgrate the final

flow as previous flow whatever the

previous flow you have with a current

residual capacity or you can say I'm

just saying it in a residual okay like

we should know why it is important so

that's why I kept bold it uh next of

that agented part next step three we

will be resting the path if the residual

capacity of the selected path is zero

means we will be like you can say if in

a class in a class uh if a teacher is

teaching you mightbe he or see knows it

well like how much assignment we can

give as a just for a you know you can

say the people will understand like

suppose uh let us take your your faculty

is giving you two assignments uh for one

week okay so it's good enough to tackle

all the problems if you can think for

each day two two different different

assignments have been given to you so

that could create a pressure this is

what uh management of pressure is all

about the network flow we reading that

one only okay so a residual capacity

like What's Your Capacity suppose you

can do uh you can read up to four hours

suppose for a day okay so the

assignments have been given to you the

assignments will take two hours so

definitely you have two Ledger hours for

other studyed okay or other study is

like you know study material you can go

for or might be network uh through

internet you can serve just think about

like you have four RS for the study you

can dedicate Max to max four arts and

four Arts is given for the

assignments so the residual capacity is

zero means you do not have any other

Arts to recaf other subjects to okay

this is what the problem is we are

actually trying to release our pressure

this is what exactly we're doing in our

Network flow okay so step four what it

has step two and step three we will be

continuing until the flow from the

source to sync is is having the residual

capacity as zero until that we will be

running it like each path we have to

focus like from source to syn whatever

the path that we are having if we'll cut

all the sours as residual capacity as

zero then we say we stopped here because

from Source we can expect there is a

flow okay if Source the path which are

connected immediate connection to the

source if the paths are having residual

capacity as zero then we cannot flow it

this is what the for focus and algorithm

says okay now we'll focus on a question

how we'll be going to solve it once it

is uh being understood by you then uh

you can say we have completed this

network Flow by finding the four FAL and

algorithm uh see these are question uh

with you can say you can expect in this

order or else a table will be given to

you where the paths are get like parts

are given with the capacity might be

okay

so here as for the question we have the

graph with us and the question is

written find the maximum flow or Max

flow through the given network using for

focus and algorithm considering non full

forward edges here no backward edges are

considered So based on a non full

forward edes how we'll find out the max

flow okay so as I said in the step one

assign all the flow initial flow as zero

okay so you can check

whenever we are writing the original

capacity will be always the right hand

side of it okay so always will keep the

right hand side as our original capacity

and the left hand side is considered as

the flow of the path of flow of the

network

okay initially we said it is zero for us

okay I'll change the color when I

picking one by one

I'll be changing the color I'm writing

here as augmented

path augmented

path next is a residual

capacity why I'm saying residual

capacity I'll be telling you that one

bottl capacity how do we find so the

bottl could be found out if the flow is

zero initially if the flow is zero there

is the capacity is 10 here the capacity

is four here the capacity is 10 so the

augmented path is this one is considered

as the augmented path there are many

augmented path could be formed not an

issue if the source and sync is there in

a path we will say it's augmented path

this is considered as a augmented

path okay there are many augmented path

could be possible if source in could be

there then we can say it's a augmented

path then the capacity is given to us as

10 41 so the minimum capacity which is

four is considered as our but

capacity okay we can say it's a but

capacity but the initial flow should be

zero then only we can say it's a but

capacity then for the residual capacity

how do we find Initial it is zero so for

this the residual will be 10 which which

is the original capacity minus the flow

is zero so the residual capacity I'm

saying it is RC residual capacity is z

10 why because 10 minus capacity minus

flow will be a residual capacity here

the residual capacity is four here the

residual capacity is 10 so out of this

the minimum residual capacity will be

considered as four so we can say the

minimum capacity residual capacity will

be uh selected okay this is how we will

be knowing the concept So based on the

uh idea we first uh you know the

prerequisites which we studied first

we'll complete this

one then only we go in depth of this

problem it's done now argumented path

like you can have a table might be the

table could be having uh four five rows

based on the augmented path which you

have selected so I'm just creating it in

such way which might be helpful for us

in future so uh whenever I'm picking so

I'm just changing the color here

initially I'm I'm just picking this as

green so whenever you are finding the

answer you always think the source to

syn the best way is this one and this

one okay so you can do one by one okay

uh so this would be better like why

because whenever we do not have any

conflict here also we can expect no

conflict whenever we are finding you

just remember the minimum capacity which

is four will be selected why because the

residual capacity is zero each augmented

path whenever we are finding always the

residual capacity of any path will be

zero we'll be finding out you can check

here I'm just putting it green so I'll

start the flow finding the flow there

here I'm finding the flow out of this

whichever the minimum residual capacity

we found we have to select this one so s

then a then B then T this is what the

augmented path is so the minimum

residual capacity is 4 here we can find

because 10 4 10 the minimum is 4 so what

we have to do we have to add it it is

written there so what we have to do

previous flow plus current residual

capacity previous flow was

Zero current residual capacity is four

so total flow will be four

this is what how we can find it out

previously the flow was zero and the

residual capacity we have selected is

four that's why it is updated as

four

okay is updated as four here also it is

updated as four why because previous

flow plus selected residual capacity

will be considered as the current flow

of this augmented clth so here I will

say the residual capacity is 4 now okay

you you could have to write it but

capacity not an issue if it initial uh

flow is zero you can write it butl

capacity sometimes we'll expect the

repetion of it that's why we can say we

have to stop there okay by saying uh

butling capacity here 4 - 4 is 0 that's

why we said we just put a circle by

making it this path could not be uh used

further why because the residual

capacity is zero you can say you can

read up to 4 4 hours and if four hours

is given as an assignment you cannot

flow like other students are having like

a to A and B to T there are two

different students who are having their

dedicating 10 hours for study and you

are dedicating 4 hours of study so the

capacity we have to maintain like 4

hours only if I'll enhance it so you

cannot you know overcome it because our

Target is the pipe shouldn't be brushed

the pipe should have its own capacity

Max to Max this much capacity could be

available not not not an issue for us if

I'll say No 5 hours of assignments you

have to do by any means there is certain

rules now you cannot go ahead of it you

have dedicated 4S means the 4S will be

dedicated to you uh the study whatever

the thing is that you have decide it Tak

4 hours means 4 hours but within the 4S

if I'll be doing so this is how we are

releasing the pressure or we are

managing the pressure okay so for this

augmented path we said residual capacity

is zero for here the residual capacity

will be considered as a original

capacity minus the flow which we

selected is this is what our residual

capacity which is RC now residual Capac

based on the residual capacity we'll be

doing but initially what we are doing we

are focusing on non-conflict one okay

like here the first one will be

non-conflict for us then this one also

non-conflict for us here the minimum we

have like 9 is a minimum why because 10

10 and 9 the minimum will be selected

okay so whenever we added to the flow

here this will be added to previous flow

plus the selected residual capacity

which is nine then you put nine here

okay so I'm just cutting this one always

you write in this like you cut this and

you write it nine the main reason of

writing this means you are updating the

flow okay this is what we are doing or

else I could have to write by omitting

this no this is not correct okay because

as for the rule which is defined we

should have to follow that

one so the augmented path is s to C then

D then T the total residual capacity is

considered as N9 here as I told you

whenever we are selecting augmented path

definitely any of these paths like four

paths could be selected five paths could

be selected definitely one augmented

means definitely the residual capacity

of any path could would be zero more

than one or at least one definitely will

have the residual capacity of zero here

you can say 9 - 9 the capacity minus

flow is zero that's why what we did like

we put a circle like we'll not choose

further because through this we cannot

go ahead like here there are three

students 9 RS is the maximum RS for a

student like he or she cannot go further

but other students have 10s so we cannot

follow the 10 Hearts we could have to

like manage the pressure so definitely

follow the last one okay whenever the

class is running smooth if all the

students will understand that doesn't

mean that only fast Venture students

will understand or second Venture

students will understand this is not

what we have to do we have to go for

like whatever the students are like 18

students or 20 students if all student

will understand then only we can go

ahead this is what the releasing of

pressure or maintaining of a class okay

next we have done this argumented path

now I'm changing the

color you can check path could be

established like based on the residual

right now we are working with the

initial zero now Fe started from source

to whether we have to like we have to

find whether there is any other path

could be established or being possible

or not here the residual capacity we

have to always keep in mind here the

residual capacity is six I'm just saying

the residual capacity by a color

whenever I'm doing the finding out the

residual capacity 10 - 4 is 6 is our

residual capacity here the residual

capacity is 8 - 0 is 8 here the residual

capacity like from this it could be a

possible Direction so from this we can

write 6 - 0 is 6 okay so here the

residual capacity we can expect is 10 -

4 which is 6 so out of this 6 8 6 then

six out of this we have the minimum one

which is six that that's why we are

focusing on the residual that's why I'm

writing it here as residual otherwise I

could have the option to write it water

leg we will work first time second time

it up to you like we can work with the

but like not an issue but further

directions of further finding the

argumented PA is based on the residual

capacity that's why I'm writing the

residual capacity in this side okay so

whenever we are going to choose this one

we have to first find out the residual

capacity so the residual capacity is 10

- 4 like original of capacity minus the

flow okay so that's why I have to select

the minimum one the minimum you can take

is this six okay or else if you have any

doubt you can check other paths too

clear so other paths suppose other paths

you are going to check this one also a

path could be established but here I

have selected this one so that's why I'm

following this path right now we have

the minimum be six I'm just using this

one as a row for us next this next this

next this this is on path we have

selected S2

a then a to T then b b to T there are

four 1 2 3 4 four edges are there so the

residual capacity we have selected is

six okay once we have selecting what we

are doing you just check

it what the residual capacity we

selected is 6 4 + 6 is 10 we have to

write there as 10 the updating value is

10 now

okay next it's previously it was Zero

now it will be updated as 6 0 + 6 is 6 6

is the flow now now

next here is zero previously existing

now we put six here previously it was

four now it will be considered as 10 why

because current residual capacity which

you found are definitely the previous

low will be added so here 10 10 we found

res capacity here we found res capacity

zero here we found residual capacity as

zero I said you know one example I have

given through which I said definitely

whenever we found an augmented path

there at least one path is considered as

the residual capacity is having zero

residual capacity having zero means we

cannot go further we cannot accommodate

further we cannot flow further with the

capacity is finalized as for the

capacity we made the flow more than

capacity flow could not be there like

like you say suppose capacity is six the

flow could not be seven for each path

definitely we have to keep in mind so

here in this path which we found is and

now changing the

color okay this is what we found as our

augmented paths and if you have any

doubt like can we do further you can

check here is the residual capacity is

one here's resal capacity Zero from here

I can switch but from here only one path

is there through which we can reach to

SN so augmented path could not be formed

that's why we have to stop it clear once

we are stopping like to find Max

flow Max flow or maximum flow the answer

could be the augmented for the residual

uh the sum sum of all the residual

capacity which you have collected

4 + 9 +

6 total is 19 this is what the answer is

the max flow or maximum flow we can find

in this uh directions first we'll keep

an augmented path whether the augmented

path could be formed well if is the

residual capacity will focus the minimum

residual capacity will be selected okay

this is how we have completed the for

Focus an algorithm and we can find out

the max flow the next video we have like

mean cut and how through mean cut how

we'll say the mean cut will be the max

FL so I hope it is understood by you so

thank you for watching have a good day