If toposort algorithms encounter a cycle, they return an edge that is part of that cycle. We can do the same in Bellman-Ford when encountering the negative cycle. This has real applications (e.g., currency arbitrage detection).
We should not reuse the Cycle type that is used by toposort algorithm and cycle detection algorithm, because the collect method would not work as expected (we want to find the negative cycle, not any cycle). But we could introduce a new type that would also have the collect method to find all edges that are part of the negative cycle.
If toposort algorithms encounter a cycle, they return an edge that is part of that cycle. We can do the same in Bellman-Ford when encountering the negative cycle. This has real applications (e.g., currency arbitrage detection).
We should not reuse the
Cycle
type that is used by toposort algorithm and cycle detection algorithm, because thecollect
method would not work as expected (we want to find the negative cycle, not any cycle). But we could introduce a new type that would also have thecollect
method to find all edges that are part of the negative cycle.