

Honestly, the MCMF tutorial #1 is too scientific to me and it's quite hard for me to understand.
Maybe it's implicitly explained in the article, but I don't get:  what is the meaning of "potential" and "reduced cost"?  what do we achieve by having "reduced cost"? (why do we need them?) 

I have implemented this algorithm and now I have my template of it. I'll think for a while to remember how does it work. I can answer your second question. By using potentials and reduced costs you keep all required properties, you need to perform Dijkstra's algorithm to find an augmenting path. 

The potential of a node k is the length of the shortest path in the graph from the source to k. Then, to reduce the costs of the graph you calculate the transformed cost of each link (u,v) adding potential[v]  potential[u].
This is made to have a graph with no negative costs, so we could find the shortest path using Disjktra instead of BellmannFord, something like:
void MinCostMaxFlow(graph, src, sink) {
// init cost with +inf, potential with 0 and tree with NULL
vector<int> cost, potential; vector<edge_t*> tree;
BellmannFord(graph, cost, tree, src);
UpdatePotentials(cost, potential);
for (path_t path; GetPath(tree, sink);) {
Augment(path);
Disjktra(graph, cost, tree, src, potential);
UpdatePotentials(cost, potential);
}
}
To update the potentials we just have to substract cost from the potential. 

I don't think the bit about potential is very well presented, so let me try to present it in words instead. Flow potentials are a way of transforming the network in a way that doesn't affect the optimal flow solution. We can then solve for the optimal solution in our new network and it will be the same as the optimal solution in the original network. The advantage of doing this is that it allows us to maintain positive edge weights, so we can use more efficient algorithms in the new network, such as Dijkstra rather than BellmanFord in the successive shortest path method.
The transformation trick is this: For each node i, assign a number π_{i} (this can be anything you want) and add this value to the cost of any edge that originates at node i and subtract it from any edge that ends at node i. Now consider a flow in this new network. Any flow that is transient at node i, will come in on an edge where the cost has been reduced by π_{i} and leave on an edge where it has been increased by π_{i}, so the cost of this flow will be the same as if you hadn't applied the potential at all. The only place that the transformation affects the cost is where the flow isn't transient at the sources and sinks, but this flow is fixed (we know how much flow is entering and leaving at the sources and sinks by the way we set up the problem). Therefore the change in cost for this particular flow caused by the transformation to our new network is independent of how the flow travels through the network. Hence an optimal solution in the original network corresponds to an optimal solution in the new one too.
The next part of the trick comes in the successive shortest paths algorithm. If we set the flow potential of each node to be equal to the cost of the shortest path from our supersource to that node, and maintain this property after each augmentation, then we end up with all the edgeweights in our graph being positive, so we can use Dijkstra's algorithm to calculate the shortest augmenting paths. 

Does this mean if I use BellmanFord for the whole thing then I don't need to care about potentials? Like:
void MinCostMaxFlow(graph, src, sink) {
BellmannFord(graph, cost, tree, src);
for (path_t path; GetPath(tree, sink);) {
Augment(path);
BellmannFord(graph, cost, tree, src);
}
}


The advantage of doing this is that it allows us to maintain positive edge weights, so we can use more efficient algorithms in the new network, such as Dijkstra rather than BellmanFord in the successive shortest path method.
Does this meas if the graph doesn't have negative weight then we don't need to care about potentials? In this case, without worrying the potentials, will Dijkstra alone still works? 

Does this mean if I use BellmanFord for the whole thing then I don't need to care about potentials?
Yes, you can do either negativecycle detection or shortest augmenting path using BellmanFord without using potentials at all.
Does this meas if the graph doesn't have negative weight then we don't need to care about potentials?
Unfortunately no. An augmenting path can travel the wrong direction down a directed edge with positive cost if there is already flow on that edge. In this case the cost is taken to be the negative of the cost if you were going the right direction. So even if you only have positive costs in your graph you still might have to consider negative costs in your shortest augmenting path code. 

I've tested (using UVA 10594) that using BellmanFord alone can work without worrying about potentials. The reason why using Dijkstra alone will fail is that: in the middle of MCMF algorithm, it is possible to have negative edge weight for the reverse flow. Thus, the "potentials" is invented so that this negative edge weight doesn't appear in the middle of MCMF and will make it run correctly. Is that correct?
The code that uses BellmanFord alone to solve 10594 is in the edit. The code that uses Dijkstra + Potentials is in Abednego's library.
Thanks all, now I know when do I need the "potentials" :) 

I think it is safe to use Dijkstra for the first time since the graph won't have reverse flow initially, otherwise Abednego's library would be wrong :). 

Thanks. I haven't notice that. 

I would like to clarify something to myself: In the method Reduce cost c_rev should be set to 0. If at input I have edge (i,j) and (j,i), for some i and j, should I made 4 edges in that case (as I understood from tutorial) or I can avoid that making (j,i) as c_rev(i,j) and (i,j) as c_rev(j,i)? I have looked at written solution and felix_halim's code placed in edit and I didn't find there something like c_rev = 0. Can someone explain me a bit more that part in the method Reduce cost.
Having found the successive shortest path we need to update node potentials. For each i in V the potential pi_i is equal to the length of the shortest paths from s to t. Is this mistyping or there really should be t? If there should be t, please, someone explain me why.
Thank you. 

Please, someone explain me how I should update costs and potentials if I find negative cycle with BellmannFord? Thank you. 

If you find a negative cycle with Bellmann Ford then you have to augment all possible flow through that cycle, and then try again. 

I am not sure I have understand, so please explain me on the example below? start_vertex end_vertex capacity cost 0 1 10 0 1 2 5 7 2 3 5 7 3 4 5 7 4 5 10 0 4 1 5 2
s is vertex 0; t is vertex 5 How I should update costs and potentials after Bellmann Ford? What I should do before start using Dijkstra? Thanks. 

First you try to run Bellmann Ford, but you find a negative cycle (1>2>3>4>1 with cost 19), so you augment through that cycle as much as you can (it reduces the cost, so it is good). The remaining graph is:
0 1 10 0 2 1 5 7 <+ 3 2 5 7 <+ 4 3 5 7 <+ (1) 4 5 10 0  1 4 5 2 <+
flow: 0, cost: 95
The edges marked with (1) are the reverse links of those we used to augment the cycle. Now, the graph have no negative cycles, so the initial potentials are:
w={0, 0, 12, 5, 2, 2}
From now on you can use Disjktra with these weights to calculate the shortest paths. The final answer is flow=5, cost=105. 
