Блог пользователя bluescorp

Автор bluescorp, история, 5 лет назад, По-английски

I just read the Ford-Fulkerson algorithm and Edmond-Karp's and Dinic's optimization on it. Should I always use Dinic for a max flow question or is Edmond Karp good enough for most of the questions? Asking this cos Edmond Karp looks relatively easy to code.

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

There is no best algorithm for max-flow problems. It all depends on the constraints of the problems.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +28 Проголосовать: не нравится

You should make your own judgment of what to use based on what you know. Here are some facts you should consider.

  • Ford-Fulkerson has complexity $$$O(E f)$$$, where $$$f$$$ is the maximum flow. In competitive programming problems, often $$$f$$$ will not be very big. For example in maximum matching between two sets of sizes $$$n$$$ and $$$m$$$, the maximum flow is bounded by $$$\min(n, m)$$$.
  • Edmonds-Karp is the same as Ford-Fulkerson except that it searches for augmenting paths with BFS instead of DFS. The importance is that it has polynomial time of $$$O(V E^2)$$$. So, even if the maximum flow can be very large, you have this guarantee that Ford-Fulkerson doesn't give you. Edmonds-Karp still has the guarantee $$$O(E f)$$$ so it won't perform worse than Ford-Fulkerson except possibly by a constant.
  • Dinic's Algorithm is an optimization on Edmonds-Karp with an improved guarantee of $$$O(V^2 E)$$$.
  • In practice, these worst-case complexities are often overestimates. In the special case of unit networks such as maximum matching, you get smaller complexity guarantees. In maximum matching, it guarantees $$$O(\sqrt V)$$$ flow iterations for a complexity of $$$O(\sqrt V E)$$$
  • These are not the only three flow algorithms and you can find other algorithms, heuristics, etc.
  • Dinic's algorithm requires more code than Ford-Fulkerson or Edmonds-Karp.
»
5 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Push-relabel