### AmericanPsycho's blog

By AmericanPsycho, history, 4 years ago, #### All I have read about flows is Edmonds Karp’s Algorithm, which works for maximum flow, but I have seen that there are better algorithms than this one, and there are different problems that maximum flow (like mincost, dinic and others), I would like a list of all the topics and algorithms that are useful for learning network flow! Comments (12)
 » To solve a network maximum flow problem you can use the Edmonds-Karp algorithm. It's a bit long, but it's easy to understand.However, like you said, there are some variation that make Edmonds-Karp not neccessarily the best option. I know there are a lot of algorithms that solve the max flow problem, but here is a list of the must used algorithms in competitive programming, and some useful topics: Edmonds-Karp Algorithm (Solves the max-flow in O(VE2)) Dinic's Algorithm (Solves the max-flow in O(V2E)) Bipartite Matching, a special case of the matching problem, which can be solved applying Edmonds-Karp via DFS. Hopcroft-Karp Algorithm, solves the bipartite matching problem with overall complexity Max Flow — Min Cut Theorem Min Cost Max Flow problem, can be solved using an Edmonds Karp variant, replacing the BFS with a fast Bellman-Ford implementation The assignment problem (and Min Weight Bipartite Matching), can be solved using min cost max flow The Hungarian Algorithm, solves the assignment problem with O(n3) complexity Push-Relabel Algorithm König's Theorem Dilworth's Theorem The last two theorems allows us to solve the Minimum Vertex Cover and Maximum Independent Set problems in bipartite graphs using flow algorithmsOne of the most important things about these kind of problems is to find that it is indeed a network flow problem. That's why these topics require a lot of practice.Personally, I find very hard to understand some algorithms like the Hungarian Method, so it is important to prepare a good library with these implementations. This way we avoid the struggle during contests!Hope you find this list useful :)