search

williamfiset / Algorithms

A collection of algorithms and data structures
MIT License
17.33k stars 4.37k forks source link

Negative cycles in min cost max flow algorithms #67

Open williamfiset opened 5 years ago

williamfiset commented 5 years ago

The current implementation of the Bellman Ford min-cost flow algorithms seems to only support non-negative edge costs, but in reality, they should be able to handle negative weighted edges.

williamfiset commented 5 years ago

I will need to investigate this more to see if the initial graph should be able to handle negative edge cost or if negative edge costs simply arise as part of the residual graph.

jishanshaikh4 commented 5 years ago

It seems like it works perfectly with negative cycles too. Bellman-Ford algorithm takes to care for negative edges for shortest cost calculation. And usually I saw at most places, it is implemented in a similar fashion. Maybe I'm wrong, feel free to correct me. For a more thorough reference, you can see at https://cp-algorithms.com/graph/min_cost_flow.html