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.
Minimum Cost Max Flow with Negative Weight Cycles?
algorithms;optimization;network flow;max flow