I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is lowered in each round. To find a negative cycle I am using the bellman-ford algorithm.
My Problem is: Bellman-ford only finds cycles that are reachable from the source, but I also need to find cycles that are not reachable.
Example: In the following network, we already applied a maximum flow. The edge $(A, B)$ makes it very expensive. In the residual network, we have a negative cost cycle with capacity $1$. Removing it, would give us a cheaper solution using edges $(A, C)$ and $(C, T)$, but we cannot reach it from the source $S$.
Labels: Flow/Capacity, Cost
Of course, I could run Bellman-ford repeatedly with each node as source, but that does not sound like a good solution. I'm a little confused because all the papers I read seem to skip this step.
Can you tell me, how to use bellman-ford to find every negative cycle (reachable or not)? And if not possible, which other algorithm do you propose?