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$ – John L. Feb 6 '19 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 '19 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 '19 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 '19 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.