= Dual network potentials from shortest-path distances
{title2=$\pi_i=-d_i,\quad c_{ij}-\pi_i+\pi_j\ge0$}
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.
Back to article page
