Sign in to watch this lesson
Advanced - Graphs · 4:32
Finding Negative Cycles (and Arbitrage)
A currency loop whose rates multiply to more than one becomes a negative cycle once every rate r is turned into the weight −log r. Starting every Bellman–Ford label at zero (a virtual source joined to every vertex) finds a negative cycle anywhere in the graph, and n parent steps from the last relaxed vertex land on the loop before we collect it. For all pairs, Floyd–Warshall marks (i, j) as −∞ when i reaches a vertex with a negative distance to itself that reaches j, and Johnson's potentials make every weight non-negative for Dijkstra.
You will learn
- Map exchange rates to weights −log r so that an arbitrage loop (product > 1) is exactly a negative cycle, and explain why 1/r does not work
- Find a negative cycle anywhere by starting every label at 0, running n phases with an epsilon comparison, and taking n parent steps before collecting the loop
- Compute all-pairs distances with Floyd–Warshall and mark the −∞ pairs through vertices with d[t][t] < 0, guarding against INF plus a negative weight
- Explain Johnson's reweighting w + h(u) − h(v) ≥ 0 and why it preserves shortest paths