1
$\begingroup$

Does there exist an algorithm that can solve the minimum cost maximum flow problem even if the residual graph contains negative weight cycles?

I have an implementation that uses shortest paths to compute the minimum cost maximum flow but this fails to find the minimum cost flow even though such a flow is well defined. This is because it uses Djikstra's to find augmenting paths and gets stuck in negative weight cycles.

I found the cycle cancelling algorithm but it seems that it will augment the flow in the graph in degenerate ways i.e. it might try to circulate flow in a cycle of negative cost even though no flow was passing through those arcs in the cycle.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ "This is because it uses Djikstra" -- sooo, don't use Dijkstra? Bellman-Ford deals with negative weights (!) perfectly and detects negative cycles. $\endgroup$ – Raphael♦ Aug 25 '16 at 9:54
  • $\begingroup$ Yes but Bellman Ford will just stop when it detects a negative weight cycle. Even thought shortest paths in a graph are not defined, a min cost flow is always well defined in a capcitated (finite capacity) residual network $\endgroup$ – Banach Tarski Aug 25 '16 at 13:06
  • 2
    $\begingroup$ Isn't having that cycle in hand enough to proceed? $\endgroup$ – Raphael♦ Aug 25 '16 at 13:22

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.