Shortest Path Problem Minimization

Question

I am asked to formulate shortest path problem as a min-cost flow problem.

The textbook I am using is Gentle Intro to Optimization where it states the max netflow model for graph G with s, t starting and ending point:

let $x_a$ be the number of bits/flow on arx a $$ maxf_x(s)$$ $$s.t. f_x(q)=0$$ $$0 \le x \le c$$

where the first constraint is flow conservation and $f_x(q)=\sum x_a~\text{entering} -\sum x_a~\text{leaving}$

So I am reversing the above model by changing max to min. But there is nothing stopping the algorithm from just giving me a 0 path answer. How can i ensure the min problem gives a shortest directed path?

Answer 1

It is always true that $$ -\max_{x} f(x) = \min_{x}( -f(x)). $$ So you could redefine the objective a bit as well and it will have the same solution, and the problem is still well-defined.

Answer 2

The shortest path is the distance traveled by one unit of flow starting at $s$ and ending at $t$. So you need to adjust your flow conservation constraints accordingly.