bluescorp's blog

Edmond-Karp or Dinic for max flow?
By bluescorp, history, 4 years ago, In English

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.

  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you know Edmond-Karp won't work for a question?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Edmonds-Karp algorithm runs in $$$O(VE^2)$$$ time

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      I don't understand why I'm getting downvoted, without being told why.

      Anyway, Dinic's runs in $$$O(V^2E)$$$ while Edmonds-Karp's runs in $$$O(VE^2)$$$. Depending on the constraints, whether there are more vertices or more edges, that you can decide the algorithm.

      Also, it's worth noticing that in practice, these algorithms can run much faster than in theory.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ratism

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        "Depending on the constraints, whether there are more vertices or more edges, that you can decide the algorithm."

        Where did you see a problem with flows where there are more vertices than edges?

        Dinic is always better than Edmonds-Karp.

        Also, there are many optimizations for Dinic, and special cases where it can be used (bipartite match or networks with unit capacities), check Wikipedia

        P.S. There is also a method to get Dinic algorithm with complexity O(E^2 log) without any hard methods, when all numbers are integers. Sorry, have only Russian article Масштабирование потока.

        → Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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.
→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Push-relabel

→ Reply