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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.