I was overwhelmed before I watched this video. Then I've thoroughly a great amount of information about Ford-Fulkerson method. And now I am excited to confidently use this method. Thank you for existing, you're a lifesaver.
I had many Problems with the Ford Felkurson Algorithmus , now after watching your video i've to the first time understood what the proffesor the hole Time in the classeroom wanted to clarify but he couldn't as well as you done ! Many thanks
I think many people are getting confused here regarding the back edge and it being non zero. For those who are having confusion, idea is to keep the inflow and outflow through a particular node same until it hits the Max capacity .And if it were to be zero you can't use it as a back edge hence back edge needs minimum 1. As long as their is equilibrium through a particular node and doesn't exceed capacity, you can change the flow as you want.
If we choose following paths, the same can be done in just 3 steps: S -> A -> B -> T = 4 S -> A -> D -> B -> T = 6 S -> C -> D -> T = 9 Which makes a total of 19 :-)
either he is himself confused and not sure why he is doing it, or he is trying to follow the concept of reverse edges of Ford-Fulkerson, but not actually inserting reverse edges
I have a doubt that....i think your way of this solution is easy ....but....the above sir solution to complex ( 3rd path with opposite flow. ). .....so both way of solving are correct or not ?
You can choose any of the paths, just follow the three rules, 1. The net flow for any vertex must be zero, inflow = outflow. 2. You can only select non-full forward edges 3. You can also only choose non-zero backward edges. After all this, whatever augmenting path you take, the final answer should match.
it has been 6 years you had commented but im still replying to it. I used the alphabet increasing order to avoid confusion on which paths i had gone through and which are not yet
sir i have doubt.. if there is path from A to D in this graph.. then how you have considered the path i.e. S->C->D->A->B->T... if there is arrow from only A to D.
It's Actual shows that there is path from D->A but, in real it changes the Quantity flowing throgh it. initial: A->B(0/4) &A->D(8/8) After: A->B(4/4) &A->D(4/8) Beacuse , Inflow is equal to Outflow.
if i were to select a forward edge A-C for a flow of 2,it will achieve its maximum capacity of 2/2. Does that mean i can for some other instance select C-A (backward edge) for 2 as well? Then will its capacity become 2-2=0? IF it becomes zero once again,does that mean one can again route a flow through A-C upto a capacity of 2 once more (as the capacity became 0 after selecting the backward edge C-A)? Could someone shed some light on this confusing aspect of ford fulkerson algo?
Path is not going from D to A in the original graph. A path is formed in the residual graph. He didn't show the residual graph. Think of it like retracting the flow that was flowing through that edge.
@@jatindersingh2260 Adding a backward flow in the edge is like reducing the forward flow in the edge. So it still holds with your reasoning. We are just sending less flow through the edge. It is fine as long as we don't send more flow in the reverse edge than the flow in the forward edge, otherwise the flow will become negative.
I thinking, there no edge from D to A, y in the third augmenting path there is an edge from D to A? does not that violate the directed graph principle?
sir i have doubt.. if there is path from A to D in this graph.. then how you have considered the path i.e. S->C->D->A->B->T... if there is srrow from only A to D🤔 pls sir clear this my doubt...
At 8:44, He chose s->A->D->B->t. At 8:51, he compared the path with s->C->D->B->t saying that we cannot proceed on s->C->D->B->t. Why we can not choose s->C->D->B->t ? I still don't get it. Thank you
That's great, but I can't understand how you choose these paths. Why did you go D->B (by a backward edge) where as some forward edges remained with 0 flow? Not clear.
You can select arbitrarily. and the backward flow was possible because the flow (8) wasn't zero. and even if you select A->B path the maximum flow will be 19 in the sink.
Thanks for this video. I understood the goal and process of this theory generally. However, i am still quite confused because the selection of the path is little chaotics.
The definition of augmenting path states that "Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the flow" . But when we select a backward edge,does that qualify as a path of positive capacity?
I get the back edge D to A and all. We can send from D to A. But in diagram 3, how can he send 4 more flow from A to D when the path has already reached it's capacity!! We can only go backward and not forward, right?
My question is that how can you say that the maximum flow will be 19 as you have chosen arbitrary paths and someone could have chosen some other arbitrary paths for which the maximum flow could have been 20. You proved that for your chosen augmented paths at the end there cannot be more flows but why not for some other chosen arbitrary augmented paths?
@7.30 minutes, step 3- augmenting path is expressed as S-C-D-A-B-T , is not possible . From A to D there is a direct connection but D to A no direct path is there.
Anyone on a clear explanation as to why the selected backward edge of the 3rd augmented path is valid? I know..he gave a rule earlier.. but can anyone explain it in simple terms maybe through a real life example or something?
No one explains the logic behind all these solutions. People are just memorising these techniques blindly. Please explain why are we doing all these things, which algorithmic paradigm are we using?
For theoretical and mathematical explanation please refer to Introduction to Algorithms by CLRS. Just keep in mind the theory of resultant force of physics while approaching this problem and try to use the anti-parallel edges as stated in the book. The concept of physics helped me to develop a strong intuition of Ford Fulkerson's Min Cut and Max Flow Algorithm.
I am so glad India exists, 90% of my knowledge came from you guys. Much thankful
from ?
@@sohamshinde1258 Indian people explaining stuff on TH-cam
@@LB-lj5wp he is asking where are u from
@@turtlepedia5149 Oh
@@sohamshinde1258 Balkans
I was overwhelmed before I watched this video.
Then I've thoroughly a great amount of information about Ford-Fulkerson method. And now I am excited to confidently use this method.
Thank you for existing, you're a lifesaver.
6 years later your videos are helping my graduate studies thank you!
at 11:45 my persistent doubt about this algorithm was vanished, thanks so much for your class. Well done. A salute from Brazil!
I feel you
@@ninistories i feel both of you
Here I am too
i feel all four of you
i feel all five of you
People like you have taken me through my computer sciences degree!
I had many Problems with the Ford Felkurson Algorithmus , now after watching your video i've to the first time understood what the proffesor the hole Time in the classeroom wanted to clarify but he couldn't as well as you done !
Many thanks
I think many people are getting confused here regarding the back edge and it being non zero. For those who are having confusion, idea is to keep the inflow and outflow through a particular node same until it hits the Max capacity .And if it were to be zero you can't use it as a back edge hence back edge needs minimum 1. As long as their is equilibrium through a particular node and doesn't exceed capacity, you can change the flow as you want.
Thanks a lot
vit aa macha??
sp; da kumenasai
Didn't understand
Aama Bro...😄@@rishinivedan2265
I was confused but after seeing your video sir, I am more confused. Thank you sir
First beautiful handwriting and second amazingly explained Thank you so much Sir.
I got confused about the back step but now I understood, thank u very much
If we choose following paths, the same can be done in just 3 steps:
S -> A -> B -> T = 4
S -> A -> D -> B -> T = 6
S -> C -> D -> T = 9
Which makes a total of 19 :-)
yes but its difficult to see the optimise path , thats why algo is there
for S***>C****D****T wouldnt you have to subtract everything by 9
Yesss
Really impressive sir !!!
I have no idea before I clear all my doubts
sir je at 6:31 why we are choosing from D to A there is dircted path for A to D not D to A????
either he is himself confused and not sure why he is doing it, or he is trying to follow the concept of reverse edges of Ford-Fulkerson, but not actually inserting reverse edges
why cant i choose s>c>d>b>t instead of s>c>d>a>b>t,is it necessary to go with the backward edge?
Mr:Arnab thank you very much you are the best one .
Another ways to clear the concept ::
Path :: SCDT -> 9
SABT -> 4
SADBT -> 6
Total max flow = 19
yes ... SABT is also possible ... will the answer be same ???
I have a doubt that....i think your way of this solution is easy ....but....the above sir solution to complex ( 3rd path with opposite flow. ). .....so both way of solving are correct or not ?
i also got the same answer, but then the solution is different for selecting different paths, this shouldn't be the case.
correct
Thanks. Very Nice, Fold up & Clear lecture. From Bangladesh .
Thank You so much, Sir, your teaching has warmth and guidance.
Is there a particular order our argumenting paths should go?
For example, why do we not do S>A>C>D>T?
You can choose any of the paths, just follow the three rules, 1. The net flow for any vertex must be zero, inflow = outflow. 2. You can only select non-full forward edges 3. You can also only choose non-zero backward edges. After all this, whatever augmenting path you take, the final answer should match.
@@anshuman17025 thank you so much dear.
it has been 6 years you had commented but im still replying to it. I used the alphabet increasing order to avoid confusion on which paths i had gone through and which are not yet
That was a really well explained video. Thank you Sir. Much love.
Sir, you explained it neatly
Thanks
Cleared many doubts. Thank You
Perfect explanation man!
This is a great explanation of working step by step!
thank you sir u are a blessing to us I really hate this algo
I hope my school can hire you as my algo professor sir. Really nice explanation.
Will I get the same answer (19), if I choose the paths in a different order, say, choosing S-C-D-T before S-A-D-T?
sir i have doubt..
if there is path from A to D in this graph..
then how you have considered the path i.e. S->C->D->A->B->T...
if there is arrow from only A to D.
It's Actual shows that there is path from D->A but, in real it changes the Quantity flowing throgh it.
initial: A->B(0/4) &A->D(8/8)
After: A->B(4/4) &A->D(4/8)
Beacuse , Inflow is equal to Outflow.
Wonderful explanation, i certainly had no doubts going into my exam after this video.
I only listen a few word but I very easy understand ...thank you I am from Việt Nam
I absolutely heard "Now Niggas discuss" at the beginning and was like WOW hold your horses D:
Lol 😆
Did you get what he actually said then?
@@Sivah_Akash he said "let us discuss"
@@vaibhavranshoor2664, I did get that. Just wanted to know if Guillermo understood it later.
if i were to select a forward edge A-C for a flow of 2,it will achieve its maximum capacity of 2/2. Does that mean i can for some other instance select C-A (backward edge) for 2 as well? Then will its capacity become 2-2=0? IF it becomes zero once again,does that mean one can again route a flow through A-C upto a capacity of 2 once more (as the capacity became 0 after selecting the backward edge C-A)?
Could someone shed some light on this confusing aspect of ford fulkerson algo?
I have choosen path s>a>b>t = 4
Then s>c>d>t =1
Then s>a>d>t = 1
Then s>a>d>b>t = 5
And got max flow 11
Is it correct??
Check 3rd path first.
How the path go back D to A in directed graph.
Think about it sir .
Path is not going from D to A in the original graph. A path is formed in the residual graph. He didn't show the residual graph. Think of it like retracting the flow that was flowing through that edge.
Same doubt
@@jatindersingh2260 Adding a backward flow in the edge is like reducing the forward flow in the edge. So it still holds with your reasoning. We are just sending less flow through the edge. It is fine as long as we don't send more flow in the reverse edge than the flow in the forward edge, otherwise the flow will become negative.
I thinking, there no edge from D to A, y in the third augmenting path there is an edge from D to A? does not that violate the directed graph principle?
Was stuck on the concept of reverse edges...I Came here...I saw....I conquered the doubt.
Very nice explanation... thanks a lot
Thank you sir. Very good explanation.
bro is just so adorable . thankyou sir!!
sir i have doubt..
if there is path from A to D in this graph..
then how you have considered the path i.e. S->C->D->A->B->T...
if there is srrow from only A to D🤔
pls sir clear this my doubt...
and wht about s>a>b>t?
@@yashwantbhagawat2710 the path s to a have reached its maximum capacity so the flow cant happen in that path
The path ure saying is wrong
Follow the arrows and reach to the sink
At 8:44, He chose s->A->D->B->t.
At 8:51, he compared the path with s->C->D->B->t saying that we cannot proceed on s->C->D->B->t.
Why we can not choose s->C->D->B->t ? I still don't get it.
Thank you
great! i'm waiting u with other tutorials
Can I please know how are we selecting the augmented paths, like are those the random paths and solving or like..??
That's great, but I can't understand how you choose these paths. Why did you go D->B (by a backward edge) where as some forward edges remained with 0 flow? Not clear.
You can select arbitrarily. and the backward flow was possible because the flow (8) wasn't zero. and even if you select A->B path the maximum flow will be 19 in the sink.
Thanks for this video. I understood the goal and process of this theory generally. However, i am still quite confused because the selection of the path is little chaotics.
If you do it on paper along with the video, you will understand. I did that and it clicked :)
Sir ur explanation is gd but in the 3rd one there is no path for the D->A but then how shall we make it plz check it out .Thank u sir...
It's a non empty backward edge so I think it's completely fine to consider it.
Intuitionally, I guess it is same as saying not to send some of those weights on that edge in the first place rather than making a reversed flow.
Thank you sir. Simple and on point.
Thanks sir 😊
Straight forward. Thank you
Thank you so much sir it's very helpful for me
The definition of augmenting path states that "Traditional network flow algorithms are based on the idea of augmenting paths, and repeatedly finding a path of positive capacity from s to t and adding it to the flow" . But when we select a backward edge,does that qualify as a path of positive capacity?
according to CLRS, for every foward edge f(u,v) a backward edge of value, f(v,u)=-f(u,v) exists
Thank u, very helpful and straight to the point 🙏
great explanation!!! Thanks a lot sir
I get the back edge D to A and all. We can send from D to A.
But in diagram 3, how can he send 4 more flow from A to D when the path has already reached it's capacity!! We can only go backward and not forward, right?
perfect lecture for network flow problem
What a clear explanation. Really impressive
i see why you have 1.3milion subscribers. nice video
the best explanation thanks
how can we take scdabt, isn't the edge directed from a to d ?
very good explanation!!!!!!!
Thank you for your efforts
Thank you. And I have a question.
What if we have 2 entrances to and 2 exits from the network? What is the modification then?
Thanks in advance.
We create a Parent source and Parent ink and connect them to all sources giving them an infinite capacity, and then proceed as normal.
If I change the order of selecting Augmenting path, will it affect the value of maximum flow?
same question!
No it doesn't change your value but you take more time to come to the same conclusion.
Thank You So Much❤
so when i use max flow min cut ,the minimum cut equals 20 so how? we say that the min cut=max flow ?
min cut is 19. try cutting from S and C as one pair of vertex and A,B,D,T as other. you will get 19 min flow
Alternate Soln:
S -> C -> D -> T
S -> A -> D -> B -> T
S -> A -> B -> T
My question is that how can you say that the maximum flow will be 19 as you have chosen arbitrary paths and someone could have chosen some other arbitrary paths for which the maximum flow could have been 20. You proved that for your chosen augmented paths at the end there cannot be more flows but why not for some other chosen arbitrary augmented paths?
You can take other paths as well but that won't change the maximum flow.
@@soumalyasahoo2664 The maximum flow will be 20,if we choosee different argument paths..
Very well explained sir thank you
@7.30 minutes, step 3- augmenting path is expressed as S-C-D-A-B-T , is not possible . From A to D there is a direct connection but D to A no direct path is there.
Thank u sir.. Extremely good.. Nice explanation
For which edges in the network, the maximum flow would increase, if their capacities are
doubled., Answer ?
Thank you sir😊❤
thanku sir u explain it too easy
Thanks it was really helpful
Thanks for the video
The magic of this video is that the bottle neck capacity of 3rd path is 'FORD'😂, hit like if you got it
How are you able to go from D to A, the graph is directed for a reason
My Question says to use labeling procedure. Plz can someone quickly answer that, is ford fulkerson's algorithm also known as labelling procedure?
thank you very much for your clear illustration.....god bless you
Anyone on a clear explanation as to why the selected backward edge of the 3rd augmented path is valid?
I know..he gave a rule earlier.. but can anyone explain it in simple terms maybe through a real life example or something?
Thank you, Sir!
Where is that video man???
thanks a lot sir.u taught clearly.nice presentation.can u put ur video for max flow min cut theorem
The minimum cut here (which is equal to the maximum flow) consists of the edges S->A & C->D
s->c->d->t = 2 why maximum is 8 ?
Is this problem present in some textbook? Another guy created a video using the same problems!
Yes.
@@amli1988, which one?
@@Sivah_Akash dasgupta
Thanks a lot sir!
Watch at 1.5x speed :)
nice video with nice suit
thanks india
Top rojla bro
Thanks for uploading this amazing video
fortiniti ila babaj?
No one explains the logic behind all these solutions.
People are just memorising these techniques blindly.
Please explain why are we doing all these things, which algorithmic paradigm are we using?
Algorithms name is Ford Fulkerson Min Cut Max flow, rest can be found on wikipedia
Someone feels like me aha
Try finding solution for the problem by yourself..... If you are able to do it, you will understand the logic☺
@@riteshpatidar9184 Then why will a person watch any video on youtube? Everything he/she will do by themselves! Dumb logic :(
For theoretical and mathematical explanation please refer to Introduction to Algorithms by CLRS. Just keep in mind the theory of resultant force of physics while approaching this problem and try to use the anti-parallel edges as stated in the book. The concept of physics helped me to develop a strong intuition of Ford Fulkerson's Min Cut and Max Flow Algorithm.
JavaScript is complimentary to and integrated with Java.
thankuuuuu sir
Thank you so much
there is no path for d to a
Abbe isiliye toh uthaya usko, back edge thi na. Ye video dekh pehle : th-cam.com/video/Tl90tNtKvxs/w-d-xo.html
there is no path from you to success either
@@ritik84629 hahahahh
Indians are always the lifesavers.
very beautiful describe
Here we go the night before examination