# Successive shortest paths with fixed costs and costs per unit

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.