Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

ddt's blog

By ddt, 5 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

»
5 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.

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

    Thanks a lot !!!

  • »
    »
    4 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.

    • »
      »
      »
      4 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.

      • »
        »
        »
        »
        4 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I guess maybe the confusion for me is partially due to ambiguity in the question I am asking.

        Namely, the distinction between finding maximum flow for a network and maximum flow for a single path. What I want to find is a list of lists of paths. Each outer list item would contain an inner list of paths, the first being a path along which you push flow through the initial network, then the subsequent inner list items would be the paths you choose to obtain maximum flow using subsequent residual networks.

        If we take the Edmonds Karp algorithm, we do a BFS to find the shortest path in terms of number of edges. Then we push the maximum for that path from source to sink. According to Edmonds Karp, it is totally fine if the capacity of some of these edges is < C (whether C is the maximum flow of a single path as described above, or the maximum flow for the network as determined by the max flow/min cut theorem). The problem with EK is that it guarantees that it will find a series of paths that produce maximum flow for a network, but is not able to uncover all solutions.

        The above solution would be tantamount to a greedy algorithm if I were to try to implement it over multiple iterations of a maximum flow problem on residual networks, wouldn't it? Does that clarify my question at all, or am I still missing something fundamental here?