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

Finding all paths with maximum flow
Автор ddt, 10 лет назад, По-английски

What should be the approach to find all paths with maximum flow? The graph is directed acyclic graph and the maximum number of nodes(vertices) in the graph can be 40 and edges around 80. Also, most of the edges have unit capacity.

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

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

Flow isn't fixed on a single path, that's quite trivial... but okay: maxflow along a path is just the minimum of capacities of its edges, so you want to find the maximum capacity c such that there's at least one path from the source to the sink (binseach+BFS) using only edges with capacity  ≥ c, then only take edges with capacity  ≥ c and find the number of paths — for DAGs, it can be found by a simple DP.

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

    Thanks a lot !!!

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

    I had the same question, but I'm not sure I understand the above answer.

    Is there any way you could expand on this Xellos? Wont this solution only find paths for a single iteration of the maximum flow problem by finding some maximum C? I guess I'm not understanding how you handle cases where leaving more in the residual graph will allow for an overall higher maximum.

    The idea of a dynamic programming solution makes sense to me, but it seems like we would still end up with a hefty exponential time (although probably improved from factorial) runtime. Any elaboration would be greatly appreciated.

    Thank you.

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

      Once you know the value of the max flow, i.e. c, as Xellos pointed out, you can calculate the number of paths from source to sink by DP. You remove all the edges with capacity  < c from the graph as they can't be on a path that provides max flow. Now, to calculate the number of paths, you can first topologically sort the graph (it's a DAG, so it's possible) and then compute the dp values in the topologically sorted order. DP[source] = 1. For all others, .

      Correct me if I am wrong.

      → Ответить