# How do I apply the Ford-Fulkerson to a minimal cost flow problem?

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 :

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 :

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?

• 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. – Robby the Belgian Nov 8 '20 at 16:47
• 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? – WindBreeze Nov 8 '20 at 16:50
• 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. – Robby the Belgian Nov 8 '20 at 16:56
• I added a super-source and a super-sink do I remove them or keep them in the final tree? – WindBreeze Nov 8 '20 at 17:01
• 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. – Robby the Belgian Nov 8 '20 at 17:52