Dual network potentials from shortest-path distances (${\pi }_i=-d_i,c_{ij}-{\pi }_i+{\pi }_j\ge 0$)

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.