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.