Graph Theory37 sections · 1633 units
Open in Course

Positive Cycles

Infinite score problem

A positive cycle is a cycle where the sum of edge weights is positive. If you can walk this cycle, you gain score each time. If there is a positive cycle on any path from room 11 to room nn, the answer is unbounded.

You can loop arbitrarily many times. To detect this, negate all edge weights and look for negative cycles using Bellman-Ford. A negative cycle in the negated graph is a positive cycle in the original graph.