I'm doing a min cost assignation problem to assign doctors to their working days for a hospital.
After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle canceling algorithm to minimze the flow's cost. I'm basically using the Bellman-Ford algorithm from the sink of the residual graph with the max flow.
The problem is that Bellman-Ford gives me one negative weight cycle (the one that reduces more the cost), and in a given example, such cycle has a bottleneck capacity of 0, so I cannot send flow around it. However in the very same example, other negative weight cycles exist with a bottleneck capacity strictly greater than 0. Sending the bottleneck flow among these cycles would certainly reduce the cost of my assignment, nevertheless the Bellman-Ford implementation does not seem to be capable of yielding such cycles.
How might I get all the graph's negative cycles, to finally get the min cost assignation?
For this university project, the algorithm's performance is not relevant.