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

Edmond-Karp or Dinic for max flow?
Автор bluescorp, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

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

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -10 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ratism

        → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        "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 Масштабирование потока.

        → Ответить
»
4 года назад, # |
  Проголосовать: нравится +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.
→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Push-relabel

→ Ответить