# Optimizing a shortest path problem

I am asked to formulate shortest path problem as a min-cost flow problem and I am stuck on the following step:

Min cost flow probelm can be formulated as https://en.wikipedia.org/wiki/Minimum-cost_flow_problem.

I am taking away the capacity constraint and the required flow constraint. But with the two constraints left, there is nothing stopping the algorithm from just giving me a 0 flow answer. How can i ensure the min problem gives a directed path?

Note: I assumed i cannot be using the constraint from shortest path which is using st-cuts>=1. That would defeat the whole purpose of the problem.

• What is your particular network problem? From the Wikipedia page you linked, as long as some flow enters your system ($d \neq 0$), the “required flow” constraints will ensure that the flow is not zero everywhere. – Ahmed S. Attaalla Apr 11 at 2:53
• in the textbook of Gentle intro to optimization, the network problem is to maximize flow through a directed graph, but the exercise asks to find shortest path using minimize flow – james black Apr 11 at 3:43

To solve a shortest $$s$$-$$t$$ path problem as a minimum-cost network flow problem, send one unit of flow from $$s$$ to $$t$$. That is, you have a supply of $$1$$ at node $$s$$, a demand of $$1$$ (or supply of $$-1$$) at node $$t$$, and supply of $$0$$ at all other nodes.
• If you consider the set of arcs in an $s$-$t$ path, you want one arc out of $s$ (and none into $s$), one arc into $t$ (and no arcs out), and for all other nodes you want one arc in and one arc out. The min-cost network flow formulation relaxes these conditions to enforce just the difference of outflow and inflow at each node, and the minimization objective discourages flows that aren’t paths. Alternatively, you can obtain the min-cost flow formulation as the dual of an LP formulation of Bellman’s equations. – RobPratt Apr 11 at 14:12