Finding paths from the result of max flow Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That is, each set of paths will make the max flow.
But I suspect there could be multiple set of such paths.
Give the edges some value of priority. Once you have run a given maxflox algorithm, reduce the priority of a given edge by the amount of flow which got through the last time. This way edges which have gotten flow through them the last time running the algorithm will not be chosen as the first flow first this time and another way, if any, will be produced.