Interpreting mincost flow dual variables Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} & \sum\limits_{i,j} f_{ij} c_{ij}, \\
s.t. & 0 \leq f_{ij} \leq q_{ij}, \\
& \sum\limits_{j=1}^n f_{kj} - \sum\limits_{i=1}^n f_{ik} = b_k, &(\forall k) \\
& b_s = b, b_t = -b, \\
& b_k = 0. & (\forall k \not \in \{s, t\})
\end{gather}}$$
Here $f_{ij}$ is the flow on the edge from $i$ to $j$, $c_{ij}$ is the cost of the edge, $q_{ij}$ is its capacity.
Its dual can be written (hopefully I'm not mistaken) roughly as
$$\boxed{\begin{gather}
\max\limits_{\lambda_{ij}, \pi_k \in \mathbb R} & \sum\limits_{i,j} \lambda_{ij} q_{ij} + b(\pi_s - \pi_t), \\
s.t. & \lambda_{ij} + \pi_i - \pi_j \leq c_{ij}, \\
& \lambda_{ij} \leq 0.
\end{gather}}$$
Is there some meaningful interpretation to the dual variables or the dual problem itself? For maximum flow, the dual reduces to minimum cut, and anything similar here? I often saw that mincost duals are called potentials, I assume they're somewhat related to Johnson potentials, but in which way exactly?
I also know that the dual can be further simplified by saturating $\lambda_{ij}$ as
$$
\lambda_{ij} = \min(0, c_{ij} - \pi_i + \pi_j),
$$
allowing the dual to be formulated simply as
$$\begin{gather}
\max\limits_{\pi_k \in \mathbb R} & \sum\limits_{i,j} \min(0, c_{ij} - \pi_i + \pi_j) q_{ij} + b(\pi_s - \pi_t).
\end{gather}$$
Unfortunately, it doesn't help me at all with interpreting it...
 A: Let $c_{ij}^\pi = c_{ij} - \pi_i + \pi_j$ be the adjusted cost of the edge $i \to j$. Consider a path
$$
i_0 \to i_1 \to \dots \to i_k
$$
and sum up the adjusted weights on the path:
$$
c_{i_0 i_1}^\pi + \dots + c_{i_{k-1} i_k}^\pi = (c_{i_0 i_1} + \dots + c_{i_{k-1} i_k}) + \pi_{i_k} - \pi_{i_0}.
$$
In particular, for $i_0 = i_k$, when the path is a cycle, the total adjusted cost is same as total initial cost.
From this and the cycle-path decomposition theorem follows that the cost of any $b$-flow on adjusted costs would exceed the cost of same $b$-flow on initial costs by exactly $b(\pi_t - \pi_s)$, so we get rid of this excess by subtracting this value from the target function.
As for the first summand, it is comprised as if all negative-cost edges are taken into the flow, bounding the minimum-cost flow from below, so maximizing it would take it as close to the actual minimum-cost flow as possible.
On the other hand, for any particular minimum-cost flow, we may define $\pi_k$ to be the shortest path to $t$ from $k$ in the residual network of the $b$-flow. Since the flow is minimum, residual network does not have negative cycles and $\pi_k$ are all well-defined. Moreover, defined this way, it holds for non-saturated edges $i \to j$ that
$$
\pi_i \leq \pi_j + c_{ij},
$$
meaning that $c_{ij}^\pi \geq 0$ for any $i,j$ such that the edge $i \to j$ was not saturated (so it could've been used in an augmenting path in the resudial network). Moreover, if the edge is in use, but not saturated, the strict equality $\pi_i = \pi_j + c_{ij}$ would hold, as it means that the edge is on some shortest path between $s$ and $t$ (otherwise it would be better to bypass it and not use at all).
Thus, among edges that participate in the minimum cost flow, only saturated edges will possibly have (negative) non-zero adjusted cost and only they would contribute to the target function, meaning that the target function, indeed, equates to the minimum cost of the flow.
