neg_cycle.hpp file
Negative cycle detection for weighted directed graphs.
This module provides an efficient algorithm for detecting negative cycles in weighted directed graphs. It implements a cycle detection method that is superior to Bellman-Ford for this specific purpose.
The algorithm works by:
- Maintaining a predecessor map to track paths
- Performing edge relaxations iteratively
- Detecting cycles in the predecessor graph
- Verifying that detected cycles are indeed negative
Classes
-
template<typename DiGraph>class NegCycleFinder
- Negative cycle finder for weighted directed graphs.