Editing Shortest path problem (section)

=== Negative cycle detection ===
In some cases, the main goal is not to find the shortest path, but only to detect if the graph contains a negative cycle. Some shortest-paths algorithms can be used for this purpose:

* The [[Bellman–Ford algorithm]] can be used to detect a negative cycle in time <math>O(|V||E|)</math>.
* Cherkassky and Goldberg<ref>{{Cite journal |last1=Cherkassky |first1=Boris V. |last2=Goldberg |first2=Andrew V. |date=1999-06-01 |title=Negative-cycle detection algorithms |url=https://doi.org/10.1007/s101070050058 |journal=Mathematical Programming |language=en |volume=85 |issue=2 |pages=277–311 |doi=10.1007/s101070050058 |s2cid=79739 |issn=1436-4646}}</ref> survey several other algorithms for negative cycle detection.