Graph Theory37 sections · 1633 units
Open in Course

Cycles Must Be On Path

Reachable from 1 and reaches n

Not all positive cycles matter. Only cycles reachable from room 11 that can reach room nn make the answer infinite. Run BFS or DFS from room 11 to find all reachable rooms. Run BFS or DFS on the reverse graph from room nn to find all rooms that can reach room nn.

A positive cycle matters only if it is in both sets. If Bellman-Ford finds a negative cycle, check if that cycle is in the intersection of these two sets.