The successive shortest path algorithm, used to solve the minimum-cost flow problem, can be described as follows :

Successive shortest path (for minimum-cost flow) :

  • while all flow is not sent :

    • compute shortest path between source and sink nodes w.r.t. arc costs (through Dijkstra's algorithm for example).

    • augment the most flow possible through this path (and add reverse arcs on this path).

    • compute reduced costs on arcs in the network (through updating node potentials).

Is computing reduced costs necessary, i.e., does the algorithm function correctly without modifying any arc costs?

Edit : The algorithm gives the same solution, with or without reduced costs computation, on some example networks done by hand.

  • 1
    $\begingroup$ "Is computing a residual network necessary, i.e., does the algorithm function correctly without changing any arc costs?" Have you run the algorithm on a few simple non-trivial examples? What have you found? $\endgroup$ – Apass.Jack Feb 6 at 22:28
  • $\begingroup$ The algorithm seems to work fine on some example networks (done by hand), both with and without updating arc costs. $\endgroup$ – J. Schmidt Feb 7 at 9:39
  • $\begingroup$ en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm - I suggest reading some textbook explanations of Ford-Fulkerson as they will typically cover why you need to use a residual network. $\endgroup$ – D.W. Feb 10 at 6:25
  • $\begingroup$ My question is focused more on the need of reduced costs in the residual network, all the other elements of a residual network are clear. I will edit my question. $\endgroup$ – J. Schmidt Feb 11 at 8:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.