from Dinic History of Algorithms for Maximum Flow
- [Ford-Fulkerson algorithm - Wikipedia https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A9%E3%83%BC%E3%83%89%E3%83%BB%E3%83%95%E3%82%A1%E3%83% AB%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%B3%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0]
- 1956
- May not stop if capacity is an unreasonable number
- If the capacity is an integer, O(Ef) with the maximum flow as f
- This is due to the increase in flow at each step.
- For rational numbers, multiply by an appropriate integer to get an integer.
- [Edmonds Karp’s algorithm - Wikipedia https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%89%E3%83%A2%E3%83%B3%E3%82%BA%E3%83%BB%E3%82%AB%E3%83%BC% E3%83%97%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0]
- 1972
- O(VE^2)
- Almost identical to Ford Fulkerson’s algorithm.
- From the start, first do a width-first search to find the distance.
- Search only in the direction away from the start when searching for increasing paths.
- Edmonds–Karp algorithm - Wikipedia
- Dinic’s algorithm - Wikipedia
- 1970
- O(V^2E)
- Almost identical to Edmonds-Karp’s algorithm.
- There are additional innovations.
- And it can even be O(VElogV).
This page is auto-translated from /nishio/最大流を求めるアルゴリズムの歴史 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.