Ford Fulkerson algorithm for Maximum Flow Problem Example

Ford Fulkerson algorithm for Maximum Flow Problem Example
Watch More Videos at
www.tutorialsp...
Lecture By: Mr. Arnab Chakraborty, Tutorials Point India Private Limited.

[@LB-lj5wp]

I am so glad India exists, 90% of my knowledge came from you guys. Much thankful

[@sohamshinde1258]

from ?

[@LB-lj5wp]

@@sohamshinde1258 Indian people explaining stuff on TH-cam

[@turtlepedia5149]

@@LB-lj5wp he is asking where are u from

[@LB-lj5wp]

@@turtlepedia5149 Oh

[@LB-lj5wp]

@@sohamshinde1258 Balkans

[@RaynerGS]

at 11:45 my persistent doubt about this algorithm was vanished, thanks so much for your class. Well done. A salute from Brazil!

[@nini-ic7is]

I feel you

[@chrisben321]

@@nini-ic7is i feel both of you

[@Framoio]

Here I am too

[@hamdidhia6573]

i feel all four of you

[@yangjiahui1213]

i feel all five of you

[@nikezofficiel]

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.

[@nobody9290]

I was confused but after seeing your video sir, I am more confused. Thank you sir

[@dhavalchheda1626]

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.

[@djrobert9207]

Thanks a lot

[@rishinivedan2265]

vit aa macha??

[@rishinivedan2265]

sp; da kumenasai

[@Ayush37262]

Didn't understand

[@jesvanths7242]

Aama Bro...😄@@rishinivedan2265

[@labandaetoilista4873]

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

[@youtubecommenter5122]

People like you have taken me through my computer sciences degree!

[@osmankhalid2005]

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 :-)

[@turtlepedia5149]

yes but its difficult to see the optimise path , thats why algo is there

[@huguesaugustin7836]

for S***>C****D****T wouldnt you have to subtract everything by 9

[@yuva2916]

Yesss

[@needleskane1370]

I got confused about the back step but now I understood, thank u very much

[@shahidsiddiqui7152]

First beautiful handwriting and second amazingly explained Thank you so much Sir.

[@mosaic34]

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?

[@Bianca-zo2dm]

Is there a particular order our argumenting paths should go?
For example, why do we not do S>A>C>D>T?

[@anshuman17025]

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.

[@uditjec8587]

@@anshuman17025 thank you so much dear.

[@swativekhande8655]

Really impressive sir !!!
I have no idea before I clear all my doubts

[@arafatahmmed263]

Another ways to clear the concept ::
Path :: SCDT -> 9
SABT -> 4
SADBT -> 6
Total max flow = 19

[@biswajeetsethi7689]

yes ... SABT is also possible ... will the answer be same ???

[@aakashsinha9641]

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 ?

[@sayanporey6127]

i also got the same answer, but then the solution is different for selecting different paths, this shouldn't be the case.

[@harshitmehra9390]

Thank You so much, Sir, your teaching has warmth and guidance.

[@mhrhabib7998]

Thanks. Very Nice, Fold up & Clear lecture. From Bangladesh .

[@halah1995]

Mr:Arnab thank you very much you are the best one .

[@guanzhaoli4917]

I hope my school can hire you as my algo professor sir. Really nice explanation.

[@devorein]

That was a really well explained video. Thank you Sir. Much love.

[@nini-ic7is]

thank you sir u are a blessing to us I really hate this algo

[@suyashjain4485]

Sir, you explained it neatly
Thanks

[@FujihiroCZ]

Perfect explanation man!

[@poetrycorner1098]

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????

[@osmankhalid2005]

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

[@AmanKumar-gq7li]

Cleared many doubts. Thank You

[@bongatonghop65]

I only listen a few word but I very easy understand ...thank you I am from Việt Nam

[@BenNelsonillegalnumbers]

This is a great explanation of working step by step!

[@hemantbohra143]

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??

[@Rothaf4759]

Wonderful explanation, i certainly had no doubts going into my exam after this video.

[@sounghwanhwang5422]

Very nice explanation... thanks a lot

[@soumalyasahoo2664]

Was stuck on the concept of reverse edges...I Came here...I saw....I conquered the doubt.

[@nasarathabdulgafoor6506]

Thank you sir. Very good explanation.

[@memoryLB]

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.

[@wirito]

If you do it on paper along with the video, you will understand. I did that and it clicked :)

[@CSEBivekKumarSahNirala]

Thank you so much sir it's very helpful for me

[@RanbirSingh-zc2du]

very good explanation!!!!!!!

[@sujitsah7223]

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.

[@amarks444]

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.

[@LvGbLiNd]

I absolutely heard "Now Niggas discuss" at the beginning and was like WOW hold your horses D:

[@Sivah_Akash]

Lol 😆

[@Sivah_Akash]

Did you get what he actually said then?

[@vaibhavranshoor2664]

@@Sivah_Akash he said "let us discuss"

[@Sivah_Akash]

@@vaibhavranshoor2664, I did get that. Just wanted to know if Guillermo understood it later.

[@vishakhabinani6856]

bro is just so adorable . thankyou sir!!

[@gechfikadu8431]

great! i'm waiting u with other tutorials

[@mohammedadel8948]

Thank you for your efforts

[@yuvashreerchan7407]

great explanation!!! Thanks a lot sir

[@shima6163]

the best explanation thanks

[@anuragdwivedi1804]

perfect lecture for network flow problem

[@nishitasingh5227]

Thanks for the video

[@yashwantbhagawat2710]

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...

[@yashwantbhagawat2710]

and wht about s>a>b>t?

[@explorewithavi9925]

@@yashwantbhagawat2710 the path s to a have reached its maximum capacity so the flow cant happen in that path

[@lavalyrics3193]

The path ure saying is wrong
Follow the arrows and reach to the sink

[@shevinweerakone3250]

Thank u, very helpful and straight to the point 🙏

[@BADKALOS]

Thank you sir. Simple and on point.

[@aaakashkumar]

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?

[@deepakbarala1521]

Check 3rd path first.
How the path go back D to A in directed graph.
Think about it sir .

[@sangramjitchakraborty7845]

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]

Same doubt

[@dkapur17]

​@@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.

[@anonym8361]

Alternate Soln:
S -> C -> D -> T
S -> A -> D -> B -> T
S -> A -> B -> T

[@MisterAadj]

i see why you have 1.3milion subscribers. nice video

[@summerbreeze9090]

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

[@jotjot3000]

thanku sir u explain it too easy

[@krantijaybhay1295]

Very well explained sir thank you

[@Nuobu-p7k]

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?

[@ssm840]

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?

[@TusharMahli123]

What a clear explanation. Really impressive

[@akilandeswaryg4666]

thanks a lot sir.u taught clearly.nice presentation.can u put ur video for max flow min cut theorem

[@НектоЛохматый]

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.

[@deepjyotide3223]

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.

[@ssm840]

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?

[@adityaranjansahoo6261]

according to CLRS, for every foward edge f(u,v) a backward edge of value, f(v,u)=-f(u,v) exists

[@bujjibabulingampalli9648]

Thank u sir.. Extremely good.. Nice explanation

[@navyasrikamireddy3753]

Can I please know how are we selecting the augmented paths, like are those the random paths and solving or like..??

[@daehyuncho1766]

nice video with nice suit

[@dhanukamallawaarachchi9538]

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.

[@priskon5950]

We create a Parent source and Parent ink and connect them to all sources giving them an infinite capacity, and then proceed as normal.

[@ShakrinJahanMozumder]

Thank you, Sir!

[@shayanbagherpour526]

Thanks it was really helpful

[@jayush8480]

Thank you Sir

[@suryag8976]

Thanks a lot sir!

[@matiahey3474]

very beautiful describe

[@debaratighatak2211]

Thank you sir😊❤

[@sujithas4295]

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...

[@SULEKHADAS-qo6mk]

@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.

[@01jojorocks]

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?

[@soumalyasahoo2664]

You can take other paths as well but that won't change the maximum flow.

[@kirane61]

@@soumalyasahoo2664 The maximum flow will be 20,if we choosee different argument paths..

[@ahmedhbaieb1973]

Top rojla bro

[@nowshintabassum2768]

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?

[@anassibrahimi7041]

The minimum cut here (which is equal to the maximum flow) consists of the edges S->A & C->D

[@shreyashdewangan7288]

thankuuuuu sir

[@Hop]

Indians are always the lifesavers.

[@govindjangid6201]

Thanks sir

[@julius-te4gp]

fortiniti ila babaj?

[@tusharverma2454]

Thanks Sir.

[@kishanlal676]

If I change the order of selecting Augmenting path, will it affect the value of maximum flow?

[@talha191995]

same question!

[@dhavalchheda1626]

No it doesn't change your value but you take more time to come to the same conclusion.

[@ammarhaiderjafri9390]

For which edges in the network, the maximum flow would increase, if their capacities are
doubled., Answer ?

[@Ahmad_Alhasanat]

If you put the flow as an arrow direction in it would be easy to understand without having write and delete

[@Autom_te]

JavaScript is complimentary to and integrated with Java.

[@wanted909090]

thank you very much for your clear illustration.....god bless you

[@kingrajput6202]

how can we take scdabt, isn't the edge directed from a to d ?

[@MJ-kl9zq]

Watch at 1.5x speed :)

[@nour_raafat]

Thank You!

[@sohamgurav7713]

The magic of this video is that the bottle neck capacity of 3rd path is 'FORD'😂, hit like if you got it

[@jyotibhardwaj293]

S,A,D,T(8) then scdt(2),sabt(2),scdbt(6),so total flow is =18 here.when we take different path,then flow is different

[@nouhabouti3256]

so when i use max flow min cut ,the minimum cut equals 20 so how? we say that the min cut=max flow ?

[@Levithan-c4z]

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

[@pisanghangus2]

thanks

[@srivatsann7193]

Where is that video man???

[@simransimran6766]

thank u sir

[@thangamanig7122]

The explanation covers 80% of the algorithm only. Any bad selection of the augmenting paths sometimes ends up with a solution lower than the maximal flow. After finishing all the flows of the augmenting paths, it is essential to check the reverse-flow augmenting paths. You are missing these important steps.

[@hannahsabir9705]

Amazing thank you

[@JayWavy-me5pq]

How are you able to go from D to A, the graph is directed for a reason

[@spikezy999]

Here we go the night before examination

[@getluckyy1006]

Perfect!

[@kshitijsabale7534]

My Question says to use labeling procedure. Plz can someone quickly answer that, is ford fulkerson's algorithm also known as labelling procedure?