ddt's blog

Finding all paths with maximum flow
By ddt, 10 years ago, In English

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.

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

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

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.

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

    Thanks a lot !!!

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

    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.

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

      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.

      → Reply