I have a directed graph $G(V,A)$ with arc costs $c_{ij} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}x_{ij}$, where $\alpha_{ij}$ and $\beta_{ij}$ are, respectively, a fixed cost and a cost per unit of flow pushed along arc $(i,j)$. I'd like to solve the minimum-cost flow (MCF) problem in this graph, i.e., given a supply/demand of $k$ units from a source node $s$ to a target node $t$, choose the flow amounts per arc, $x_{ij}$, that minimize the total cost $c_x = \sum_{(i,j)\in A}c_{ij}$ of the flow. I chose the successive shortest path algorithm for this task:
Successive Shortest Path
1 Add arcs (s',s) and (t,t') with capacity = k and cost = 0
2 Initial flow x = 0
3 while ( G_x contains a path from s' to t' ) do
4 Find any shortest path p from s' to t'
5 Augment current flow x along p
6 Update G_x
where $G_x$ is the residual graph obtained after pushing flow $x$ in $G$. However, I have a simple doubt about this:
- If the amounts of flow per arc $x_{ij}$ are only known after the algorithm runs, how can I correctly define the costs of arcs in $G_x$ to find the shortest paths?
I assume I can estimate the costs as $\hat{c_{ij}} = \alpha_{ij}1_{x_{ij}>0} +\beta_{ij}C$ for some constant value $C$, but to confirm it I need proof that a solution which is optimal w.r.t. the total estimated cost $\hat{c_x}$ is also optimal w.r.t. the real cost $c_{x}$. I could not easily come up with such a proof.
