Your videos are phenomenal. The crisp step by step visual representations of the algorithm and concise explanations helped my understanding immensely. Thanks so much.
日本にはDinic法の解説をする記事がほぼなかった。この動画は本当に分かりやすくて助かる。 (There are few lectures about Dinic's algorithm in Japan so I am very happy to find this very straightforward video. Thanks!! )
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
10:13 I love when I see Israelis come up in CS videos!!! It’s crazy to think that my professors probably know these guys. (AVL being the chief example)
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 ??
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?
While the goal of the algorithm is to find the maximum flow, it helps to speed up the algorithm if we just look at the path that makes progress, progress as in reaching the sink as fast as we can in an unweight graph. This way, instead of visiting at most E edges in traditional bfs iteration, we only have to visit up to at most V vertices, by only considering the fastest path. This reduces the time complexity from O(E) per iteration down to O(V) per iteration, this is faster as in any sensible flow problems, there will always be more edges than there are vertices.
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
![NISAMANEE - TADA (ท้าดา) [ OFFICIAL MV ]](http://i.ytimg.com/vi/hcQHEPMmJpU/mqdefault.jpg)
Just found out this Dinitz guy is a professor at my school, sitting a few doors away as I watch this.
Blew my mind.
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?
@@Linaiz he just quit in the end of 2019 it seemes he taught at ben gurion university
I also study CS in Israel (Bar-Ilan), who is this professor? Where does he teach?
It's Ben Gurion University in Israel
Hats Off man. Finally found a perfect video to learn Dinic properly.
Your videos are phenomenal. The crisp step by step visual representations of the algorithm and concise explanations helped my understanding immensely. Thanks so much.
You made me love this algorithm. Thank you!
my complements to the chef. really well made video, deserves a subscription :)
Top notch explaination, that to with a source code helps in visualizing things more better. Thank you so much:))))
日本にはDinic法の解説をする記事がほぼなかった。この動画は本当に分かりやすくて助かる。 (There are few lectures about Dinic's algorithm in Japan so I am very happy to find this very straightforward video. Thanks!! )
You explain really well. Keep making such good videos.
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
10:13 I love when I see Israelis come up in CS videos!!! It’s crazy to think that my professors probably know these guys. (AVL being the chief example)
Thank you very much! :-) Great and easy to understand explanation.
I was rather confused why Shimon Even calls 'Dinic's algorithm', 'Dinitz's algorithm' in his book. Thanks for clarifying it!
Thanks a lot, love the explanation
Thank you, this is helpful!
Nice video, you helped my a lot with understanding of graph theory algorithms, thank you
But you also considered the backwards/side edge in the second iteration. The dead end path you mentioned has a backwards edge right ?
best ed video I have ever seen
Thank you very much for this helpful video.
Thanks a lot !!! it was great help , very short and nice video.
thes the edges need to go from L to L+1 or can it also go from L to L+2??
Much appreciated!
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
??
Typically I add two nodes to be the source and the sink
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?
While the goal of the algorithm is to find the maximum flow, it helps to speed up the algorithm if we just look at the path that makes progress, progress as in reaching the sink as fast as we can in an unweight graph. This way, instead of visiting at most E edges in traditional bfs iteration, we only have to visit up to at most V vertices, by only considering the fastest path. This reduces the time complexity from O(E) per iteration down to O(V) per iteration, this is faster as in any sensible flow problems, there will always be more edges than there are vertices.
@yamyamyum may god bless you
really helpful!
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
Thank you sir.
thanks for these videos
thank you very much !
Awesome!
huge video
I love you!
I need practical application for dinic algorithm in practice
Can anyone tell me?
Network Flow : Max Flow Min Cut
.