0
$\begingroup$

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it.

I need your help and suggestions.

Thanks in advance!

$\endgroup$
  • 1
    $\begingroup$ Hint: both shortest path and min-cost flow determine the minimum of a sum. Try to establish a mapping between the sums. We can't really help you further until you demonstrate that you actually know what these algorithms mean and show your attempts at encoding one into the other. It sincerely sounds like you might not even understand each algorithm itself, since once you do, working out the connection is pretty straightforward. $\endgroup$ – DanielV Mar 12 '16 at 19:39
  • 1
    $\begingroup$ Write them both down as an LP and you see the connection. $\endgroup$ – Erwin Kalvelagen Mar 12 '16 at 21:29
1
$\begingroup$

I found an article on wikipedia where it explains how to reduce the minimum cost flow to a Shortest Path Problem: https://en.wikipedia.org/wiki/Minimum-cost_flow_problem :

The solution is to remove the capacity constraint.

$\endgroup$

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.