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$
2
  • $\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, 2020 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, 2020 at 3:43

1 Answer 1

Reset to default
1
$\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.

$\endgroup$
2
  • $\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, 2020 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, 2020 at 14:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .