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.
Between a node with Sx and a node Tx choose Tx first if you can.
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:
Every arc with a flow that is below the capacity is included in the partial tree.
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?
