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.

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 201 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 185 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 176 |

10 | -is-this-fft- | 171 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/26/2021 13:49:52 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

csuch 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 ≥cand find the number of paths — for DAGs, it can be found by a simple DP.Thanks a lot !!!

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.

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 <cfrom 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.

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?