Negative Cycle
Definition
A negative cycle has a sum of its edge weights below zero.
In a weighted graph, repeatedly traversing a reachable negative cycle can continuously reduce the total cost. Then, no finite shortest value exists for affected paths.
Simply explained
A cycle subtracts additional points from the path cost with each round.
Why it matters in practice
This is important for shortest path algorithms and consistency checks.
Example from business
Hypothetical example: A planning model detects contradictory costs via a cycle.
Limits and pitfalls
- Not every negative edge forms a negative cycle. Reachability and target relevance must be considered.
Origin & history
The term belongs to graph theory and algorithms like Bellman-Ford.
Use in mid-sized companies
- SMEs can use this to detect errors in weighted planning or optimization models.
Frequently asked questions
Can Dijkstra correctly handle negative cycles?
The algorithm is not designed for that.
Sources
- negative_edge_cycle — · NetworkX: negative_edge_cycle —
Editorially reviewed on: