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.