Handling negative cycles in graphs

1
votes

We all know that none of Bellman-Ford and Floyd-Warshall algorithms can't handle negative weight cycles, but detect them only. Is there any graph algorithm which could, or would still give correct result in presence of negative cycles?

1
algorithmgraph-theory
If there are negative cycles, then the optimal path is cycling and cycling, so there is not really a correct (finite) solution then. - Willem Van Onsem
What would you want to get as a result? Cost of shortest non-intersecting path? - Juan Carlos Ramirez

1 Answers

0
votes

The network simplex method may do what you want, though it's notably more complicated. https://www.cs.upc.edu/~erodri/webpage/cps/theory/lp/network/slides.pdf

Methods exist for eliminating negative cost cycles though I can't think of their names at the moment.