e2298's blog

By e2298, history, 4 years ago, In English

How do I find the actual flow (on each edge) that generates the maximum flow? i.e. the flow function. I'd prefer a solution using the Edmonds-Karp algorithm, but any other is fine too.

I think it should be simple and I'm feeling pretty stupid for not finding it. Can I get the flow from the residual graph? do I need to keep track of it in a separate data structure?

I thought the answer might be the difference between the initial capacity of the edge in the flow network and the value in the residual graph after running the algorithm, but I have a feeling that doesn't work.

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

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You are correct. It is simply the list of edges with a positive flow after running the algorithm.