Dinic's Algorithm | Network Flow | Graph Theory

Explanation of Dinic's network flow algorithm
Next Video: • Dinic's Algorithm | Ne...
Ford Fulkerson explanation video:
• Max Flow Ford Fulkerso...
Ford Fulkerson source code video:
• Max Flow Ford Fulkerso...
Algorithms repository:
github.com/williamfiset/algor...
Video slides:
github.com/williamfiset/Algor...
Personal website:
www.williamfiset.com
===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix
Support me by purchasing the full graph theory course on Udemy which includes additional problems, exercises and quizzes not available on TH-cam:
www.udemy.com/course/graph-th...

[@ohadyeger5583]

Just found out this Dinitz guy is a professor at my school, sitting a few doors away as I watch this.
Blew my mind.

[@Linaiz]

Haha wow!! I'm thinking about doing my master's in CS in Israel. May I know the name of the school? Do you recommend it?

[@almogz9486]

@@Linaiz he just quit in the end of 2019 it seemes he taught at ben gurion university

[@spano1723]

I also study CS in Israel (Bar-Ilan), who is this professor? Where does he teach?

[@ohadyeger5583]

It's Ben Gurion University in Israel

[@sarwarjahan05]

Hats Off man. Finally found a perfect video to learn Dinic properly.

[@tylerlozano152]

Your videos are phenomenal. The crisp step by step visual representations of the algorithm and concise explanations helped my understanding immensely. Thanks so much.

[@LucasGomesDantas]

You made me love this algorithm. Thank you!

[@mohammedkhandwawala6758]

You explain really well. Keep making such good videos.

[@brainrs2732]

my complements to the chef. really well made video, deserves a subscription :)

[@jirifrantal2236]

Thank you very much! :-) Great and easy to understand explanation.

[@MrSasanaga]

日本にはDinic法の解説をする記事がほぼなかった。この動画は本当に分かりやすくて助かる。　(There are few lectures about Dinic's algorithm in Japan so I am very happy to find this very straightforward video. Thanks!! )

[@Parakak]

Thank you very much for this helpful video.

[@kiranboddeda4121]

Top notch explaination, that to with a source code helps in visualizing things more better. Thank you so much:))))

[@sharathnair1702]

Thanks a lot, love the explanation

[@AyushSingh-pq5wf]

Thanks a lot !!! it was great help , very short and nice video.

[@matianblob]

Nice video, you helped my a lot with understanding of graph theory algorithms, thank you

[@ilovancristian]

Thank you, this is helpful!

[@vagelispsimenos]

Much appreciated!

[@real_potatohead1970]

really helpful!

[@mitsumeru4954]

I was rather confused why Shimon Even calls 'Dinic's algorithm', 'Dinitz's algorithm' in his book. Thanks for clarifying it!

[@k.alipardhan6957]

thanks for these videos

[@narendratejasvi6037]

Thank you sir.

[@nguyenthanhhien3333]

thank you very much !

[@apaarkamal1301]

best ed video I have ever seen

[@Why_I_am_a_theist]

at 7:10 , is that '3' node also a dead end ? If not then why, and what do we actually have to do with the dead ends. Delete those vertex or all the edges in the dfs

[@MrZH6]

Awesome!

[@saiachyuth3460]

But you also considered the backwards/side edge in the second iteration. The dead end path you mentioned has a backwards edge right ?

[@longvu2033]

can we avoid all dead end if when we DFS, we DFS from T with reversed edge and we just take the level from L to L - 1 ?

[@AkshayAradhya]

The extra DFS is not even needed. When building the level graph, you can simply store an aditional parent node for every node. So once you reach the sink, just traverse backwards using the parent graph

[@xhamadeex]

I love you!

[@TruongNguyen-pl9cd]

thes the edges need to go from L to L+1 or can it also go from L to L+2??

[@Andy-yh7jk]

huge video

[@LLuckyy]

1 question
If u have a graph
Do u add two new vertices and label them source and sink
Or label 2 of the vertices that already exist as source and sink
??

[@WilliamFiset-videos]

Typically I add two nodes to be the source and the sink

[@Why_I_am_a_theist]

what is the intuition behind Level graph , 3:43 you said 'as quickly as possible' but that's not what we want , we want to have maximum flow so there can be a possible path which moves backwards and give us an additional flow . So why Level graph aims at only reaching quickly?

[@tuongvile9817]

I need practical application for dinic algorithm in practice
Can anyone tell me?

[@ritikagupta8847]

Network Flow : Max Flow Min Cut

[@amielwexler1165]

.