I have the following graph : What is in red is the demand/supply.

When positive -> Supply

When negative -> Demand

When $0$ -> Transfer

On each arc there is residual capacity/given flow.

The goal here is to find the maximum amount of flow we can pass through this graph and afterwards minimize the cost.


My first instinct is to create a super-source et super-sink. I get this graph : graph with super-source and super-sink

I also have the following policy that I have to respect while trying to find an augmenting path:

1.If you have a choice between S1...S2 always choose the one with the lowest number (here it's 1 so S1 will be chosen to be part of the augmenting path). Same thing for T1...T2 and D1...D2.

  1. Between a node with Sx and a node Tx choose Tx first if you can.

  2. Between a node with Tx and a node Dx choose Dx first if you can.

After applying the algorithm I get :

graph with ford-dulkerson algorithm

With this solution I'm supposed to find a partial tree that will be a base solution for the minimal cost flow problem. I'm told that I should find this tree by applying those rules:

  1. Every arc with a flow that is below the capacity is included in the partial tree.

  2. If not all nodes are in the tree add arbitrary arcs to the tree.

However if I follow 1. I get a cycle in my graph because of S1 and S3 is left out.

How do I find the correct partial tree to use? Also, should I remove the super-source and the super-sink? enter image description here

  • $\begingroup$ Your answer is correct. When it says "tree", that should not be taken too strictly. Every path from source to sink should be cycle-free, that is all. Note that with a single source and single sink, you should expect cycles in the resulting graph. $\endgroup$ – Robby the Belgian Nov 8 '20 at 16:47
  • $\begingroup$ I made a mistake in the last graph by forgetting to include the arc from T2 to D1. However, adding it creates a cycle, right? What am I doing wrong? $\endgroup$ – WindBreeze Nov 8 '20 at 16:50
  • $\begingroup$ It's not a directed cycle, so it's OK. Consider a simple graph with 1 source, 1 sink and two other nodes, arranged in a square, where all edges have capacity 10. Avoiding (undirected) cycles is not always possible. As long as you don't have any directed cycles, it's good. $\endgroup$ – Robby the Belgian Nov 8 '20 at 16:56
  • $\begingroup$ I added a super-source and a super-sink do I remove them or keep them in the final tree? $\endgroup$ – WindBreeze Nov 8 '20 at 17:01
  • $\begingroup$ Personally, I would remove them. That means you will no longer have a tree, but it also means that everything in your solution has a physical meaning. $\endgroup$ – Robby the Belgian Nov 8 '20 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.