title: In a Max Flow problem, how to find all possible sets of paths that give max flow?
body: <p>I understand that <a href="https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/" rel="noreferrer">Ford-Fulkerson Algorithm</a> can find the maximum flow that can flow from source (<code>s</code>) to sink (<code>t</code>) in a flow network.<br>
  But is there an algorithm that finds all possible sets of paths that give the max flow?</p>
  
  <p>An example:<br>
  In this network below, all edges have a capacity of 1. It's not hard to see that the max flow from <code>s</code> to <code>t</code> is 3. But how to find the combinations of paths that carry that flow? </p>
  
  <p>Expected outputs:<br>
  Path set 1: <code>s-0-1-t, s-2-3-t, s-5-6-t</code><br>
  Path set 2: <code>s-0-1-t, s-2-4-t, s-5-6-t</code><br>
  Path set 3: <code>s-0-3-t, s-2-4-t, s-5-6-t</code><br>
  Path set 4: <code>s-0-4-t, s-2-3-t, s-5-6-t</code>  </p>
  
  <p><img src="https://i.stack.imgur.com/CkZc2.png" alt="enter image description here"></p>
  
  <p>A similar question was asked <a href="https://cs.stackexchange.com/questions/13403/finding-paths-from-the-result-of-max-flow">here</a> but didn't seem to get a clear answer.</p>