The mincost flow does not use the expensive edge with cost 3.
Road system, water pipes, or data networks are the motivation for a class of optimisation problems termed flow problems. The shared characteristic for this type of system is that some kind of resource has to be transported over the edges of a graph, which are constrained to only carry only up to a certain amount of flow. For some instances edges also have other properties, making it useful to assign a cost for using a specific edge  for example variable toll charges in a network of highways.
In this kind of setting it is interesting to compute how a certain flow can be routed through the network using the cheapest possible route. This problem is called the minimumcost flow problem.
Node  
Source node  
Target node  
Edge with flow 7, cap 10 and cost 1  
Edge in residual graph, cost 1  
Edge on negative cycle, cost 1 
Please click on a node in the network to select it as the source/starting node $s$. The flow is going to start from this node. It will have no incoming flow and the outgoing flow is equal to the flowsize.
Please click on a node in the network to select it as the target/sink node $t$. The flow ends in this node. The incoming flow of this node is equal to the flowsize and it has no outgoing flow.
Now the algorithm can begin. Please click on next to start it.
The algorithm computes the maximal flow, while ignoring the cost information, using the EdmondsKarp algorithm, which is an implementation of the FordFulkerson method.
The algorithm works as follows:
As long as there is a path in the residual network from the source $s$ to the sink $t$ with available capacity on all edges in the path, the algorithm sends flow along the shortest path until the edge with the smallest capacity saturates. The shortest path is found by using a breath first search. The algorithm repeats those steps until there is no augmenting path (path with available capacity) from $s$ to $t$ left.
More detailed description of the FordFulkerson method and initialization of a maximal flow can be found here.
When the algorithm has found the maximal flow $f(s,t)$ , it builds the residual network ${G}_{f}$ corresponding to this flow as follows:
Each edge $(v,w)\in G$ is replaced by two new edges $(v,w)$ and $(w,v)$.
The edge $(v,w)$ has cost $c(v,w)$ and residual capacity $r(v,w)=u(v,w)f(v,w)>0$ , where $u(v,w)$ is the capacity of the edge and $f(v,w)$ is the flow through this edge.
The second edge $(w,v)$ has cost $c(w,v)=c(v,w)$ and residual capacity $r(w,v)=f(v,w)>0$.
The main loop repeatedly identifies negative cycles (i.e. cycles whose total weight is negative) in the residual graph.
If no negative cycle is found the algorithm terminates.
One finds negative cycles in the residual network by running the BellmanFord algorithm as follows:
If $N$ is the number of nodes in the network, the algorithm is first executed $N1$ times and should have found the shortest path from $s$ to $t$ . Then the algorithm is executed one more time and if the shortest path found in the $(N1)$th execution has not changed, then there are no negative costdirected cycles. Otherwise the algorithm takes a node the distance of which has changed, and goes from it via its ancestores until a cycle $W$ is found. $W$ is the negative cycle we were looking for.
More information on the BellmanFord algorithm can be found here.
When the algorithm finds a negative cycle, it augments
$$\delta :=min\{r(v,w):(v,w)\in W\}$$units of flow in the cycle $W$ to saturate the edge with the minimal residual capacity, so the negative cycle $W$ is removed from the residual network.
Then the algorithm goes back to the main loop to examine the residual graph for other negative cycles.
The algorithm terminated with maximal flow of:

and minimal cost for the flow:
The residual network contains no negative costdirected cycles, therefore a minimum cost flow has been found.
s ← pick(v)
t ← pick(v)
BEGIN

 (* Initialize max flow *)
 CALCULATE MAX FLOW $f(s,t)$ IN THE NETWORK
 USING THE FORDFULKERSON ALGORITHM

 (* Main Loop *)
 WHILE (the residual network ${G}_{f}$
  contans a negative cycle) DO
 
  EXECUTE BELLMANFORD ALGORITHM TO
  IDENTIFY A NEGATIVE CYCLE $W$;
  IF (negative cycle exists)THEN
   IDENTIFY cycleedges $(v,w)\in W$
   $\delta :=min\{r(v,w):(v,w)\in W\}$
  ENDIF
  FOR ($(v,w)\in W$)
   $f(v,w)=f(v,w)+\delta $
  ENDFOR
 
 ENDWHILE

END
cycle  adjustment 

   
You can open another browser window to read another tab in parallel.
Node  
Source node  
Target node  
Edge in residual graph, cost 1  
Edge on negative cycle, cost 1 
Please click on a node in the network to select it as the source/starting node $s$. The flow is going to start from this node. It will have no incoming flow and the outgoing flow is equal to the flowsize.
Please click on a node in the network to select it as the target/sink node $t$. The flow ends in this node. The incoming flow of this node is equal to the flowsize and it has no outgoing flow.
Now the algorithm can begin. Please click on next to start it.
The algorithm computes the maximal flow, while ignoring the cost information, using the EdmondsKarp algorithm, which is an implementation of the FordFulkerson method.
When the algorithm has found the maximal flow $f(s,t)$ , it builds the residual network ${G}_{f}$ corresponding to this flow.
The main loop repeatedly identifies negative cycles (i.e. cycles whose total weight is negative) in the residual graph.
If no negative cycle is found the algorithm terminates.
The algorithm runs the BellmanFord algorithm to find negative cycles in the residual network ${G}_{f}$.
When the algorithm finds a negative cycle, it augments
$$\delta :=min\{r(v,w):(v,w)\in W\}$$units of flow in the cycle $W$ to saturate the edge with the minimal residual capacity, so the negative cycle $W$ is removed from the residual network.
Then the algorithm goes back to the main loop to examine the residual graph for other negative cycles.
The algorithm terminated. The residual network contains no negative costdirected cycles, therefore a minimum cost flow has been found.
s ← pick(v)
t ← pick(v)
BEGIN

 (* Initialize max flow *)
 CALCULATE MAX FLOW $f(s,t)$ IN THE NETWORK
 USING THE FORDFULKERSON ALGORITHM

 (* Main Loop *)
 WHILE (the residual network ${G}_{f}$
  contans a negative cycle) DO
 
  EXECUTE BELLMANFORD ALGORITHM TO
  IDENTIFY A NEGATIVE CYCLE $W$;
  IF (negative cycle exists)THEN
   IDENTIFY cycleedges $(v,w)\in W$
   $\delta :=min\{r(v,w):(v,w)\in W\}$
  ENDIF
  FOR ($(v,w)\in W$)
   $f(v,w)=f(v,w)+\delta $
  ENDFOR
 
 ENDWHILE

END
The algorithm will be executed normally, but will stop in a few places. Then you will have to predict, what the algorithm would do next.
Hint: Recall the description of the algorithm.
You can open another browser window to read the description in parallel.
Knoten  
S/T Knoten  
Kante mit Kapazität 10 und Fluss 7.  
Kante im Residualgraphen.  
Kante auf augmentierendem Pfad. 
In the following exercise you will get different networks \(N\) with the respective capacities, flow values and costs \(u(e)\), \(f(e)\) and \(c(e)\) for all edges \(e \in E\), based on a current flow \(f\).
Your task is to fill the missing residual capacities \(r(e')\) bzw. \(r(e'')\) of the out and ingoing edges \(e'\) und \(e''\) in the corresponding residual network ${N}_{f}$.
You will get a network with current flow. Your task is to fill out the missing residual capacities and costs in the residual network!
Tip: Before you start read the information on residual networks again.
WARNING!
You can set the missing residual capacities and costs only once. When a value is set it can not be changed any more.
Good Luck!
You can open another browser window to read another tab in parallel.