Network dual potential (${\pi }_i$)

A vertex potential in the dual of an uncapacitated minimum-cost flow yields the edge inequalities ${\pi }_i-{\pi }_j\le c_{ij}$. Its objective is ${\sum }_i{\pi }_i{b}_i$. Adding a common constant leaves all network reduced costs and the objective unchanged when total net supply is zero. Potentials tight on a spanning tree are fixed up to this common constant.

In a directed network with no negative-cost directed cycle, add a source having zero-cost arcs to all vertices and compute shortest-path distances $d_i$. The inequalities $d_j\le d_i+c_{ij}$ make ${\pi }_i=-d_i$ dual feasible for uncapacitated minimum-cost flow. Shortest-path tree arcs are tight. An arbitrary spanning tree also fixes tight candidate potentials up to a constant, but it does not guarantee the non-tree inequalities; these must be checked.

With the tail-positive incidence convention, a network edge's reduced cost is $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$. For uncapacitated minimum-cost flow, dual feasibility requires $r_{ij}\ge 0$ and complementary slackness requires $f_{ij}{r}_{ij}=0$. A negative non-tree reduced cost identifies an improving graph cycle pivot in the network simplex algorithm. This sign convention differs from the row-column potentials of a transportation problem.