Ford Fulkerson algorithm for Maximum Flow Problem Example

Ford Fulkerson algorithm for Maximum Flow Problem Example
Watch More Videos at
www.tutorialspoint.com/videot...
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 KZbin

[@turtlepedia5149]

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

[@LB-lj5wp]

@@turtlepedia5149 Oh

[@LB-lj5wp]

@@sohamshinde1258 Balkans

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

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

[@youtubecommenter5122]

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

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

[@harshitmehra9390]

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

[@needleskane1370]

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

[@halah1995]

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

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

[@swativekhande8655]

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

[@guanzhaoli4917]

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

[@suyashjain4485]

Sir, you explained it neatly Thanks

[@shahidsiddiqui7152]

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

[@BenNelsonillegalnumbers]

This is a great explanation of working step by step!

[@mhrhabib7998]

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

[@devorein]

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

[@bongatonghop65]

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

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

[@nini-ic7is]

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

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

[@AmanKumar-gq7li]

Cleared many doubts. Thank You

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

[@Rothaf4759]

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

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

[@anuragdwivedi1804]

perfect lecture for network flow problem

[@akilandeswaryg4666]

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

[@krantijaybhay1295]

Very well explained sir thank you

[@nasarathabdulgafoor6506]

Thank you sir. Very good explanation.

[@BADKALOS]

Thank you sir. Simple and on point.

[@muhammadashrafali1975]

Thanks sir 😊

[@FujihiroCZ]

Perfect explanation man!

[@CSEBivekKumarSahNirala]

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

[@gechfikadu8431]

great! i'm waiting u with other tutorials

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

[@jotjot3000]

thanku sir u explain it too easy

[@soumalyasahoo2664]

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

[@shayanbagherpour526]

Thanks it was really helpful

[@yuvashreerchan7407]

great explanation!!! Thanks a lot sir

[@sounghwanhwang5422]

Very nice explanation... thanks a lot

[@anassibrahimi7041]

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

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

[@TusharMahli123]

What a clear explanation. Really impressive

[@bujjibabulingampalli9648]

Thank u sir.. Extremely good.. Nice explanation

[@shevinweerakone3250]

Thank u, very helpful and straight to the point 🙏

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

[@mohammedadel8948]

Thank you for your efforts

[@vishakhabinani6856]

bro is just so adorable . thankyou sir!!

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

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

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

[@shima6163]

the best explanation thanks

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

[@rokster98]

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

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

[@MisterAadj]

i see why you have 1.3milion subscribers. nice video

[@nishitasingh5227]

Thanks for the video

[@hannahsabir9705]

Amazing thank you

[@user-kw8iw8qd1b]

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?

[@RanbirSingh-zc2du]

very good explanation!!!!!!!

[@kshitijsabale7534]

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

[@wanted909090]

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

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

[@user-lc7ku6je1o]

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.

[@navyasrikamireddy3753]

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

[@Ahmad_Alhasanat]

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

[@thatipelli1]

Thanks for uploading this amazing video

[@raja-cn2ks]

Thank you sir

[@user-uy1sl4sk3f]

Thank you, Sir!

[@anonym8361]

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

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

[@ashwanikumar4288]

It's a non empty backward edge so I think it's completely fine to consider it.

[@muratcan__22]

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.

[@matiahey3474]

very beautiful describe

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

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

[@MJ-kl9zq]

Watch at 1.5x speed :)

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

[@suryag8976]

Thanks a lot sir!

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

[@srivatsann7193]

Where is that video man???

[@kingrajput6202]

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

[@JayWavy-me5pq]

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

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

[@nouhabouti3256]

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

[@nour_raafat]

Thank You!

[@ammarhaiderjafri9390]

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

[@sohamgurav7713]

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

[@antisocialmaity609]

thanks sir

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

[@mdrukonuzzaman8347]

delivering lecture was very nice but video quality specially while focusing on the white board was extremely unclear .

[@UCS_Diksantpaul]

Sir why didnt u choose s-a-b-t nd

[@shreyashdewangan7288]

thankuuuuu sir

[@tusharverma2454]

Thanks Sir.

[@simranjitsingh-bb2hd]

Augmented lect😊

[@daehyuncho1766]

nice video with nice suit

[@Autom_te]

JavaScript is complimentary to and integrated with Java.

[@estebansalami6274]

beautiful

[@simransimran6766]

thank u sir

[@ahmedhbaieb1973]

Top rojla bro

[@sayantaniguha8519]

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?

[@Ilya_4276]

Perfect

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

[@user-su7no7is7g]

best.