# Shortest Path Problem Minimization

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?

## 2 Answers

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.

• how would i redefine it? like min=-max(-f(x))? but i have to use this min to formulate shortest path, so how does this gaurantee me finding a shortest path? Commented Apr 11, 2020 at 4:18

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.