0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ahmed S. Attaalla Apr 11 at 2:53
  • $\begingroup$ 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 $\endgroup$ – james black Apr 11 at 3:43
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ can you explain the intuition behind that? i formulated the problem like you said but dont understand why the three conditions (flow conserve, f(s)=1, f(t)=-1) will find us a shortest path $\endgroup$ – james black Apr 11 at 9:06
  • $\begingroup$ 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. $\endgroup$ – RobPratt Apr 11 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.