Bellman-Ford Algorithm - Learning Module

Loading content...

0/276

Negative Cycle Detection — Bellman-Ford's Superpower

Detecting the Impossible: When Shortest Paths Don't Exist

Imagine you're building a currency arbitrage detection system. You model exchange rates as a graph where each edge represents a conversion, and you're searching for profitable trading cycles. Suddenly, the Bellman-Ford algorithm reports 'negative cycle detected.'

Congratulations—you've found money.

This is Bellman-Ford's superpower: not only does it find shortest paths with negative edges, but it also detects when shortest paths don't exist because a negative cycle makes distances unbounded. This capability has profound implications for arbitrage detection, network loop identification, scheduling feasibility analysis, and constraint satisfaction problems.

What You Will Learn

By the end of this page, you will understand exactly how Bellman-Ford detects negative cycles, why the V-th iteration check works mathematically, how to identify which specific vertices are affected by negative cycles, and the real-world applications of this detection capability.

Negative Cycles — A Rigorous Definition

Before diving into detection, let's establish a precise understanding of negative cycles and their implications.

Definition:

A negative cycle (also called a negative-weight cycle) is a cycle in a directed or undirected graph where the sum of edge weights is strictly negative.

Formally, a cycle C = (v₀, v₁, v₂, ..., vₖ, v₀) is a negative cycle if:

$$\sum_{i=0}^{k} w(v_i, v_{i+1 \mod (k+1)}) < 0$$

Example:

A --(-3)--> B --(1)--> C --(1)--> A

Cycle: A → B → C → A Total weight: -3 + 1 + 1 = -1 < 0

This is a negative cycle. Traversing A → B → C → A reduces total path cost by 1 each time.

Why Negative Cycles Break Shortest Paths:

Consider finding the shortest path from S to any vertex reachable from the negative cycle:

First, find some path from S to a vertex v on the cycle
Traverse the cycle once: total cost decreases by |cycle weight|
Traverse again: cost decreases more
Traverse n times: cost decreases by n × |cycle weight|
As n → ∞, path cost → -∞

Mathematical consequence: The infimum of path costs is -∞, meaning no finite shortest path exists.

Semantic consequence: The shortest path problem is undefined for destinations reachable from a negative cycle (that's reachable from the source).

What about destinations not reachable from the cycle?

If a vertex t cannot be reached from any vertex on the negative cycle, then shortest paths to t are still well-defined. The cycle doesn't affect t's distance. Sophisticated implementations distinguish these cases.

Reachability Matters

A negative cycle only invalidates shortest paths to vertices reachable FROM the cycle. Three conditions must hold for a vertex t's shortest path to be undefined: (1) the source can reach the cycle, (2) the cycle exists, and (3) the cycle can reach t. If any condition fails, dist[t] may still have a valid finite value.

The Detection Mechanism — Why the V-th Iteration Works

Bellman-Ford's negative cycle detection is elegant: after running V-1 iterations (which is sufficient for all shortest paths in a cycle-free graph), run one more iteration. If any edge can still be relaxed, a negative cycle exists.

The Logic:

Premise: After V-1 iterations, all shortest paths using at most V-1 edges are correctly computed.

Observation: In a graph without negative cycles, all shortest paths are simple (no repeated vertices), hence have at most V-1 edges.

Implication: If no negative cycle exists, V-1 iterations compute all shortest paths, and a V-th iteration produces no changes.

Contrapositive: If the V-th iteration produces any change (some edge relaxes), then there must be non-simple 'shortest paths'—which means a negative cycle exists.

Formal Proof:

Claim: If the V-th iteration of Bellman-Ford relaxes any edge, the graph contains a negative cycle reachable from the source.

Proof:

Suppose edge (u, v) relaxes in the V-th iteration. This means:

dist[v] > dist[u] + w(u, v)
After relaxation: dist[v] = dist[u] + w(u, v)

Let Pᵤ be the path achieving dist[u] (consisting of predecessor pointers back to source). After V-1 iterations, Pᵤ correctly represents a shortest path to u... but wait, this path might now have more than V-1 edges!

If we trace predecessor pointers from v back to source, and this 'path' has V or more edges, it must repeat some vertex (by pigeonhole principle). Let x be a repeated vertex. The subpath from x's first occurrence to x's second occurrence is a cycle.

Why must this cycle be negative?

Consider the state after iteration k where Pᵤ had length k. After iteration k+1, if we can still improve via (u, v), we're finding ever-shorter 'paths' by potentially using cycles. The only way 'shortest paths' keep getting shorter is if cycles provide benefit—i.e., negative cycles.

More rigorously: if all cycles were non-negative, simple paths would suffice, V-1 iterations would compute all shortest paths, and no improvement would be possible in iteration V. Contradiction.

negative_cycle_detection.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def bellman_ford_with_cycle_detection(graph, source):
    """
    Bellman-Ford with explicit negative cycle detection.
    
    Returns:
        (True, dist, pred) if no negative cycle
        (False, affected_vertices) if negative cycle exists
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    # Initialize
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    # Build edge list
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations (standard Bellman-Ford)
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # V-th iteration: detect negative cycle
    cycle_detected = False
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            cycle_detected = True
            break
    
    if not cycle_detected:
        return (True, dist, pred)
    else:
        # Find vertices affected by negative cycle
        affected = find_affected_vertices(graph, edges, dist, V)
        return (False, affected)
 
 
def find_affected_vertices(graph, edges, dist, V):
    """
    Identifies all vertices whose shortest path is affected by
    a negative cycle (shortest path = -infinity).
    """
    affected = set()
    
    # Run V more iterations to propagate -inf through the graph
    # Any vertex that gets updated in these iterations is affected
    dist_copy = dist.copy()
    
    for _ in range(V):
        for u, v, weight in edges:
            if dist_copy[u] != float('inf') and dist_copy[u] + weight < dist_copy[v]:
                dist_copy[v] = dist_copy[u] + weight
                affected.add(v)
    
    return affected

Finding All Affected Vertices

Detecting that a negative cycle exists is just the first step. For many applications, we need to know which vertices have undefined (−∞) shortest paths.

The Key Insight:

After V-1 iterations, if we continue running more iterations, the distances to affected vertices will keep decreasing. Vertices not affected by negative cycles will stabilize.

Algorithm for Finding Affected Vertices:

Run V-1 standard iterations
Run V additional 'detection' iterations
Any vertex whose distance is updated in these additional iterations is affected
Propagate: if v is affected and there's an edge (v, w), then w is also affected

Why V additional iterations?

The negative cycle affects vertices reachable from it. After V more iterations, the 'affected' status propagates through the entire reachable subgraph (since shortest paths have at most V-1 edges, V iterations guarantee full propagation).

find_cycle_and_affected.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
def find_negative_cycle_vertices(graph, source):
    """
    Finds the vertices that lie on a negative cycle,
    not just those affected by it.
    
    Returns:
        Set of vertices that are part of a negative cycle
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # Find an edge that can still be relaxed
    cycle_start = None
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            # v is reachable from a negative cycle
            # Follow predecessors V times to ensure we're on the cycle
            cycle_start = v
            break
    
    if cycle_start is None:
        return set()  # No negative cycle
    
    # Follow predecessor pointers V times to guarantee we're on the cycle
    current = cycle_start
    for _ in range(V):
        current = pred[current]
    
    # Now current is definitely on the cycle
    # Trace the cycle
    cycle_vertices = set()
    cycle_vertices.add(current)
    next_v = pred[current]
    while next_v != current:
        cycle_vertices.add(next_v)
        next_v = pred[next_v]
    
    return cycle_vertices
 
 
def reconstruct_negative_cycle(graph, source):
    """
    Returns the actual negative cycle as a list of vertices.
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # Find starting point for cycle trace
    cycle_start = None
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            pred[v] = u
            cycle_start = v
            break
    
    if cycle_start is None:
        return []  # No cycle
    
    # Go back V times to ensure we're on the cycle
    current = cycle_start
    for _ in range(V):
        current = pred[current]
    
    # Trace the cycle
    cycle = [current]
    next_v = pred[current]
    while next_v != current:
        cycle.append(next_v)
        next_v = pred[next_v]
    cycle.append(current)  # Complete the cycle
    cycle.reverse()  # Get forward direction
    
    return cycle

The V-Step Trick

When we find a vertex v that can still be relaxed, we know v is reachable from a negative cycle—but v might not be ON the cycle. By following predecessor pointers V times, we're guaranteed to land on the actual cycle (since the cycle has at most V vertices, we must revisit one).

Complete Worked Example: Detecting a Negative Cycle

Let's trace through a graph containing a negative cycle.

Graph Structure:

         S ----5----> A ----2----> B
                      ↑           |
                      |          3
                     -5           ↓
                      |           C
                      +----(-1)---+

Edges:

(S, A, 5)
(A, B, 2)
(B, C, 3)
(C, A, -5)

Vertices: S, A, B, C (V = 4) Iterations needed: V - 1 = 3, plus 1 for detection

Cycle Check:

A → B → C → A has weight: 2 + 3 + (-5) = 0 (not negative)
Wait, that's not a negative cycle!

Let me adjust the example:

Corrected Edges:

(S, A, 5)
(A, B, 2)
(B, C, 1)
(C, A, -5)

Cycle Check:

A → B → C → A: 2 + 1 + (-5) = -2 ✓

This is a negative cycle!

Initialization:

dist = {S: 0, A: ∞, B: ∞, C: ∞}
pred = {S: None, A: None, B: None, C: None}

Iteration 1:

(S, A, 5): dist[A] = 0 + 5 = 5 ✓
(A, B, 2): dist[B] = 5 + 2 = 7 ✓
(B, C, 1): dist[C] = 7 + 1 = 8 ✓
(C, A, -5): dist[A] = min(5, 8 + (-5)) = min(5, 3) = 3 ✓

After Iteration 1: dist = {S: 0, A: 3, B: 7, C: 8}

Iteration 2:

(S, A, 5): dist[A] = min(3, 0 + 5) = 3 (no change)
(A, B, 2): dist[B] = min(7, 3 + 2) = 5 ✓
(B, C, 1): dist[C] = min(8, 5 + 1) = 6 ✓
(C, A, -5): dist[A] = min(3, 6 + (-5)) = min(3, 1) = 1 ✓

After Iteration 2: dist = {S: 0, A: 1, B: 5, C: 6}

Iteration 3 (V-1 = 3):

(S, A, 5): dist[A] = min(1, 0 + 5) = 1 (no change)
(A, B, 2): dist[B] = min(5, 1 + 2) = 3 ✓
(B, C, 1): dist[C] = min(6, 3 + 1) = 4 ✓
(C, A, -5): dist[A] = min(1, 4 + (-5)) = min(1, -1) = -1 ✓

After Iteration 3: dist = {S: 0, A: -1, B: 3, C: 4}

Iteration 4 (Detection Iteration):

(S, A, 5): dist[A] = min(-1, 0 + 5) = -1 (no change)
(A, B, 2): dist[B] = min(3, -1 + 2) = min(3, 1) = 1 ✓ RELAXATION!

🚨 NEGATIVE CYCLE DETECTED! 🚨

We found that edge (A, B) can still be relaxed after V-1 iterations. This proves a negative cycle exists and is reachable from the source.

The cycle: A → B → C → A with total weight = 2 + 1 + (-5) = -2

Every traversal of this cycle reduces total distance by 2. Distances to A, B, and C are all undefined (−∞).

Distances Keep Decreasing

Notice how A's distance went from ∞ → 5 → 3 → 1 → -1, and would continue to -3, -5, -7, ... if we kept iterating. The negative cycle is 'pumping' ever-smaller distances into the system. This is why we must detect and report the cycle rather than continuing to iterate.

Real-World Applications of Negative Cycle Detection

Negative cycle detection isn't just an algorithmic curiosity—it solves real problems across multiple domains.

Applications of Negative Cycle Detection
Domain	Graph Model	Negative Cycle Meaning
Currency Arbitrage	Currencies as vertices, exchange rates as -log(rate) edge weights	Cycle with negative sum = profitable trading loop
Network Routing (BGP)	Routers as vertices, policies as weights	Routing loop that should not exist
Constraint Satisfaction	Variables as vertices, constraints as edges	Unsatisfiable constraint system
Scheduling	Tasks as vertices, dependencies as edges	Impossible deadline requirements
Game Exploits	Game states as vertices, actions as edges	Infinite resource generation bug

Deep Dive: Currency Arbitrage Detection

This is the classic application. Given n currencies with pairwise exchange rates, find a sequence of exchanges that yields profit.

The Transformation:

Create a vertex for each currency
For each exchange rate r(A → B), create edge A → B with weight -log(r)
Run Bellman-Ford from any vertex
If negative cycle detected: arbitrage exists!

Why logarithms?

Converting USD → EUR → JPY → USD multiplies exchange rates: r₁ × r₂ × r₃

Profitable if: r₁ × r₂ × r₃ > 1

Taking logs: log(r₁) + log(r₂) + log(r₃) > 0

Negating: -log(r₁) + (-log(r₂)) + (-log(r₃)) < 0

This is precisely a negative cycle in our transformed graph!

currency_arbitrage.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import math
 
def detect_arbitrage(currencies, exchange_rates):
    """
    Detects if arbitrage opportunity exists.
    
    Args:
        currencies: List of currency codes, e.g., ['USD', 'EUR', 'GBP']
        exchange_rates: Dict mapping (from, to) -> rate
                       e.g., {('USD', 'EUR'): 0.85, ('EUR', 'USD'): 1.18, ...}
    
    Returns:
        (has_arbitrage, cycle) - cycle is the arbitrage sequence if found
    """
    # Build graph with -log weights
    graph = {c: [] for c in currencies}
    for (src, dst), rate in exchange_rates.items():
        weight = -math.log(rate)  # Negative log of exchange rate
        graph[src].append((dst, weight))
    
    # Run Bellman-Ford from arbitrary starting currency
    source = currencies[0]
    V = len(currencies)
    
    dist = {c: float('inf') for c in currencies}
    dist[source] = 0
    pred = {c: None for c in currencies}
    
    edges = [(u, v, w) for u in graph for v, w in graph[u]]
    
    # V-1 iterations
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
    
    # Detect negative cycle
    cycle_vertex = None
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            cycle_vertex = v
            break
    
    if cycle_vertex is None:
        return (False, [])
    
    # Reconstruct cycle
    current = cycle_vertex
    for _ in range(V):
        current = pred[current]
    
    cycle = [current]
    next_v = pred[current]
    while next_v != current:
        cycle.append(next_v)
        next_v = pred[next_v]
    cycle.append(current)
    cycle.reverse()
    
    # Calculate profit multiplier
    profit = 1.0
    for i in range(len(cycle) - 1):
        profit *= exchange_rates[(cycle[i], cycle[i + 1])]
    
    return (True, cycle, profit)
 
# Example usage:
currencies = ['USD', 'EUR', 'GBP', 'JPY']
rates = {
    ('USD', 'EUR'): 0.85, ('EUR', 'USD'): 1.20,
    ('EUR', 'GBP'): 0.86, ('GBP', 'EUR'): 1.17,
    ('GBP', 'USD'): 1.40, ('USD', 'GBP'): 0.72,
    ('USD', 'JPY'): 110,  ('JPY', 'USD'): 0.0091,
    ('EUR', 'JPY'): 129,  ('JPY', 'EUR'): 0.0078,
    ('GBP', 'JPY'): 150,  ('JPY', 'GBP'): 0.0067,
}
 
has_arb, cycle, profit = detect_arbitrage(currencies, rates)
if has_arb:
    print(f"Arbitrage found: {' -> '.join(cycle)}")
    print(f"Profit multiplier: {profit:.4f}x")

Market Efficiency

In real financial markets, arbitrage opportunities are rare and short-lived. High-frequency trading algorithms detect and exploit them within milliseconds, eliminating the opportunity. The 'no negative cycle' condition is essentially the efficient market hypothesis expressed graph-theoretically!

Difference Constraints — Another Powerful Application

Bellman-Ford has a beautiful theoretical application: solving systems of difference constraints.

What are difference constraints?

A system of difference constraints is a set of inequalities of the form:

xᵢ - xⱼ ≤ cᵢⱼ

where xᵢ and xⱼ are variables and cᵢⱼ is a constant.

Example system:

x₁ - x₂ ≤ 3
x₂ - x₃ ≤ -1
x₃ - x₁ ≤ 5

The graph transformation:

For each constraint xᵢ - xⱼ ≤ c, create an edge j → i with weight c.

Why? If we find shortest path distances d[i], they satisfy:

d[i] ≤ d[j] + c (the relaxation condition)
Which rearranges to: d[i] - d[j] ≤ c

This is exactly our constraint! The shortest path distances are a solution to the constraint system.

What negative cycles mean for constraints:

If the constraint graph has a negative cycle, the system is unsatisfiable. Why?

A negative cycle through vertices v₁, v₂, ..., vₖ, v₁ corresponds to constraints:

xᵥ₂ - xᵥ₁ ≤ c₁
xᵥ₃ - xᵥ₂ ≤ c₂
...
xᵥ₁ - xᵥₖ ≤ cₖ

Adding all constraints: (xᵥ₂ - xᵥ₁) + (xᵥ₃ - xᵥ₂) + ... + (xᵥ₁ - xᵥₖ) ≤ c₁ + c₂ + ... + cₖ

Left side telescopes to 0: 0 ≤ c₁ + c₂ + ... + cₖ

But if c₁ + c₂ + ... + cₖ < 0 (negative cycle), we get: 0 ≤ (negative number)

Contradiction! The system has no solution.

Bellman-Ford tells us:

No negative cycle → Solution exists (shortest path distances are a valid assignment)
Negative cycle → No solution exists

Scheduling Applications

Task scheduling with constraints like 'Task A must finish at least 2 hours before Task B starts' are difference constraints. Bellman-Ford directly computes valid schedules or proves impossibility. This connects graph algorithms to constraint programming and operations research.

Summary: The Power of Cycle Detection

We've thoroughly explored Bellman-Ford's negative cycle detection capability:

Key Takeaways

•Negative cycles make shortest paths undefined — Traversing a negative cycle infinitely yields arbitrarily negative path lengths.
•The V-th iteration detects cycles — If any edge can still be relaxed after V-1 iterations, a negative cycle exists.
•Finding affected vertices requires propagation — Run V additional iterations to identify all vertices reachable from negative cycles.
•Cycle reconstruction traces predecessors — Following predecessor pointers V times from an affected vertex lands on the actual cycle.
•Currency arbitrage is the classic application — Negative cycles in rate graphs represent profitable trading opportunities.
•Difference constraints connect to satisfiability — Negative cycles correspond to unsatisfiable constraint systems.

What's Next:

The next page analyzes Bellman-Ford's time complexity in depth. We'll understand why it's O(V × E), compare this to Dijkstra's O((V + E) log V), and explore optimizations like SPFA that improve average-case performance while maintaining worst-case guarantees.

Page Complete

You now understand how Bellman-Ford detects negative cycles, why this detection is mathematically sound, and the practical applications ranging from arbitrage detection to constraint satisfaction. Next, we'll analyze the algorithm's time complexity rigorously.

Negative Cycle Detection — Bellman-Ford's Superpower

Detecting the Impossible: When Shortest Paths Don't Exist

Congratulations—you've found money.

What You Will Learn

Negative Cycles — A Rigorous Definition

Before diving into detection, let's establish a precise understanding of negative cycles and their implications.

Definition:

A negative cycle (also called a negative-weight cycle) is a cycle in a directed or undirected graph where the sum of edge weights is strictly negative.

Formally, a cycle C = (v₀, v₁, v₂, ..., vₖ, v₀) is a negative cycle if:

$$\sum_{i=0}^{k} w(v_i, v_{i+1 \mod (k+1)}) < 0$$

Example:

A --(-3)--> B --(1)--> C --(1)--> A

Cycle: A → B → C → A Total weight: -3 + 1 + 1 = -1 < 0

This is a negative cycle. Traversing A → B → C → A reduces total path cost by 1 each time.

Why Negative Cycles Break Shortest Paths:

Consider finding the shortest path from S to any vertex reachable from the negative cycle:

First, find some path from S to a vertex v on the cycle
Traverse the cycle once: total cost decreases by |cycle weight|
Traverse again: cost decreases more
Traverse n times: cost decreases by n × |cycle weight|
As n → ∞, path cost → -∞

Mathematical consequence: The infimum of path costs is -∞, meaning no finite shortest path exists.

Semantic consequence: The shortest path problem is undefined for destinations reachable from a negative cycle (that's reachable from the source).

What about destinations not reachable from the cycle?

Reachability Matters

The Detection Mechanism — Why the V-th Iteration Works

The Logic:

Premise: After V-1 iterations, all shortest paths using at most V-1 edges are correctly computed.

Observation: In a graph without negative cycles, all shortest paths are simple (no repeated vertices), hence have at most V-1 edges.

Implication: If no negative cycle exists, V-1 iterations compute all shortest paths, and a V-th iteration produces no changes.

Contrapositive: If the V-th iteration produces any change (some edge relaxes), then there must be non-simple 'shortest paths'—which means a negative cycle exists.

Formal Proof:

Claim: If the V-th iteration of Bellman-Ford relaxes any edge, the graph contains a negative cycle reachable from the source.

Proof:

Suppose edge (u, v) relaxes in the V-th iteration. This means:

dist[v] > dist[u] + w(u, v)
After relaxation: dist[v] = dist[u] + w(u, v)

Why must this cycle be negative?

More rigorously: if all cycles were non-negative, simple paths would suffice, V-1 iterations would compute all shortest paths, and no improvement would be possible in iteration V. Contradiction.

negative_cycle_detection.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def bellman_ford_with_cycle_detection(graph, source):
    """
    Bellman-Ford with explicit negative cycle detection.
    
    Returns:
        (True, dist, pred) if no negative cycle
        (False, affected_vertices) if negative cycle exists
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    # Initialize
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    # Build edge list
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations (standard Bellman-Ford)
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # V-th iteration: detect negative cycle
    cycle_detected = False
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            cycle_detected = True
            break
    
    if not cycle_detected:
        return (True, dist, pred)
    else:
        # Find vertices affected by negative cycle
        affected = find_affected_vertices(graph, edges, dist, V)
        return (False, affected)
 
 
def find_affected_vertices(graph, edges, dist, V):
    """
    Identifies all vertices whose shortest path is affected by
    a negative cycle (shortest path = -infinity).
    """
    affected = set()
    
    # Run V more iterations to propagate -inf through the graph
    # Any vertex that gets updated in these iterations is affected
    dist_copy = dist.copy()
    
    for _ in range(V):
        for u, v, weight in edges:
            if dist_copy[u] != float('inf') and dist_copy[u] + weight < dist_copy[v]:
                dist_copy[v] = dist_copy[u] + weight
                affected.add(v)
    
    return affected

Finding All Affected Vertices

Detecting that a negative cycle exists is just the first step. For many applications, we need to know which vertices have undefined (−∞) shortest paths.

The Key Insight:

After V-1 iterations, if we continue running more iterations, the distances to affected vertices will keep decreasing. Vertices not affected by negative cycles will stabilize.

Algorithm for Finding Affected Vertices:

Run V-1 standard iterations
Run V additional 'detection' iterations
Any vertex whose distance is updated in these additional iterations is affected
Propagate: if v is affected and there's an edge (v, w), then w is also affected

Why V additional iterations?

find_cycle_and_affected.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
def find_negative_cycle_vertices(graph, source):
    """
    Finds the vertices that lie on a negative cycle,
    not just those affected by it.
    
    Returns:
        Set of vertices that are part of a negative cycle
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # Find an edge that can still be relaxed
    cycle_start = None
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            # v is reachable from a negative cycle
            # Follow predecessors V times to ensure we're on the cycle
            cycle_start = v
            break
    
    if cycle_start is None:
        return set()  # No negative cycle
    
    # Follow predecessor pointers V times to guarantee we're on the cycle
    current = cycle_start
    for _ in range(V):
        current = pred[current]
    
    # Now current is definitely on the cycle
    # Trace the cycle
    cycle_vertices = set()
    cycle_vertices.add(current)
    next_v = pred[current]
    while next_v != current:
        cycle_vertices.add(next_v)
        next_v = pred[next_v]
    
    return cycle_vertices
 
 
def reconstruct_negative_cycle(graph, source):
    """
    Returns the actual negative cycle as a list of vertices.
    """
    vertices = list(graph.keys())
    V = len(vertices)
    
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    pred = {v: None for v in vertices}
    
    edges = []
    for u in graph:
        for v, weight in graph[u]:
            edges.append((u, v, weight))
    
    # V-1 iterations
    for i in range(V - 1):
        for u, v, weight in edges:
            if dist[u] != float('inf') and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                pred[v] = u
    
    # Find starting point for cycle trace
    cycle_start = None
    for u, v, weight in edges:
        if dist[u] != float('inf') and dist[u] + weight < dist[v]:
            dist[v] = dist[u] + weight
            pred[v] = u
            cycle_start = v
            break
    
    if cycle_start is None:
        return []  # No cycle
    
    # Go back V times to ensure we're on the cycle
    current = cycle_start
    for _ in range(V):
        current = pred[current]
    
    # Trace the cycle
    cycle = [current]
    next_v = pred[current]
    while next_v != current:
        cycle.append(next_v)
        next_v = pred[next_v]
    cycle.append(current)  # Complete the cycle
    cycle.reverse()  # Get forward direction
    
    return cycle

The V-Step Trick

Complete Worked Example: Detecting a Negative Cycle

Let's trace through a graph containing a negative cycle.

Graph Structure:

         S ----5----> A ----2----> B
                      ↑           |
                      |          3
                     -5           ↓
                      |           C
                      +----(-1)---+

Edges:

(S, A, 5)
(A, B, 2)
(B, C, 3)
(C, A, -5)

Vertices: S, A, B, C (V = 4) Iterations needed: V - 1 = 3, plus 1 for detection

Cycle Check:

A → B → C → A has weight: 2 + 3 + (-5) = 0 (not negative)
Wait, that's not a negative cycle!

Let me adjust the example:

Corrected Edges:

(S, A, 5)
(A, B, 2)
(B, C, 1)
(C, A, -5)

Cycle Check:

A → B → C → A: 2 + 1 + (-5) = -2 ✓

This is a negative cycle!

Initialization:

dist = {S: 0, A: ∞, B: ∞, C: ∞}
pred = {S: None, A: None, B: None, C: None}

Iteration 1:

(S, A, 5): dist[A] = 0 + 5 = 5 ✓
(A, B, 2): dist[B] = 5 + 2 = 7 ✓
(B, C, 1): dist[C] = 7 + 1 = 8 ✓
(C, A, -5): dist[A] = min(5, 8 + (-5)) = min(5, 3) = 3 ✓

After Iteration 1: dist = {S: 0, A: 3, B: 7, C: 8}

Iteration 2:

(S, A, 5): dist[A] = min(3, 0 + 5) = 3 (no change)
(A, B, 2): dist[B] = min(7, 3 + 2) = 5 ✓
(B, C, 1): dist[C] = min(8, 5 + 1) = 6 ✓
(C, A, -5): dist[A] = min(3, 6 + (-5)) = min(3, 1) = 1 ✓

After Iteration 2: dist = {S: 0, A: 1, B: 5, C: 6}

Iteration 3 (V-1 = 3):

(S, A, 5): dist[A] = min(1, 0 + 5) = 1 (no change)
(A, B, 2): dist[B] = min(5, 1 + 2) = 3 ✓
(B, C, 1): dist[C] = min(6, 3 + 1) = 4 ✓
(C, A, -5): dist[A] = min(1, 4 + (-5)) = min(1, -1) = -1 ✓

After Iteration 3: dist = {S: 0, A: -1, B: 3, C: 4}

Iteration 4 (Detection Iteration):

(S, A, 5): dist[A] = min(-1, 0 + 5) = -1 (no change)
(A, B, 2): dist[B] = min(3, -1 + 2) = min(3, 1) = 1 ✓ RELAXATION!

🚨 NEGATIVE CYCLE DETECTED! 🚨

We found that edge (A, B) can still be relaxed after V-1 iterations. This proves a negative cycle exists and is reachable from the source.

The cycle: A → B → C → A with total weight = 2 + 1 + (-5) = -2

Every traversal of this cycle reduces total distance by 2. Distances to A, B, and C are all undefined (−∞).

Distances Keep Decreasing

Real-World Applications of Negative Cycle Detection

Negative cycle detection isn't just an algorithmic curiosity—it solves real problems across multiple domains.

Applications of Negative Cycle Detection
Domain	Graph Model	Negative Cycle Meaning
Currency Arbitrage	Currencies as vertices, exchange rates as -log(rate) edge weights	Cycle with negative sum = profitable trading loop
Network Routing (BGP)	Routers as vertices, policies as weights	Routing loop that should not exist
Constraint Satisfaction	Variables as vertices, constraints as edges	Unsatisfiable constraint system
Scheduling	Tasks as vertices, dependencies as edges	Impossible deadline requirements
Game Exploits	Game states as vertices, actions as edges	Infinite resource generation bug

Deep Dive: Currency Arbitrage Detection

This is the classic application. Given n currencies with pairwise exchange rates, find a sequence of exchanges that yields profit.

The Transformation:

Create a vertex for each currency
For each exchange rate r(A → B), create edge A → B with weight -log(r)
Run Bellman-Ford from any vertex
If negative cycle detected: arbitrage exists!

Why logarithms?

Converting USD → EUR → JPY → USD multiplies exchange rates: r₁ × r₂ × r₃

Profitable if: r₁ × r₂ × r₃ > 1

Taking logs: log(r₁) + log(r₂) + log(r₃) > 0

Negating: -log(r₁) + (-log(r₂)) + (-log(r₃)) < 0

This is precisely a negative cycle in our transformed graph!

currency_arbitrage.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
import math
 
def detect_arbitrage(currencies, exchange_rates):
    """
    Detects if arbitrage opportunity exists.
    
    Args:
        currencies: List of currency codes, e.g., ['USD', 'EUR', 'GBP']
        exchange_rates: Dict mapping (from, to) -> rate
                       e.g., {('USD', 'EUR'): 0.85, ('EUR', 'USD'): 1.18, ...}
    
    Returns:
        (has_arbitrage, cycle) - cycle is the arbitrage sequence if found
    """
    # Build graph with -log weights
    graph = {c: [] for c in currencies}
    for (src, dst), rate in exchange_rates.items():
        weight = -math.log(rate)  # Negative log of exchange rate
        graph[src].append((dst, weight))
    
    # Run Bellman-Ford from arbitrary starting currency
    source = currencies[0]
    V = len(currencies)
    
    dist = {c: float('inf') for c in currencies}
    dist[source] = 0
    pred = {c: None for c in currencies}
    
    edges = [(u, v, w) for u in graph for v, w in graph[u]]
    
    # V-1 iterations
    for _ in range(V - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                pred[v] = u
    
    # Detect negative cycle
    cycle_vertex = None
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            cycle_vertex = v
            break
    
    if cycle_vertex is None:
        return (False, [])
    
    # Reconstruct cycle
    current = cycle_vertex
    for _ in range(V):
        current = pred[current]
    
    cycle = [current]
    next_v = pred[current]
    while next_v != current:
        cycle.append(next_v)
        next_v = pred[next_v]
    cycle.append(current)
    cycle.reverse()
    
    # Calculate profit multiplier
    profit = 1.0
    for i in range(len(cycle) - 1):
        profit *= exchange_rates[(cycle[i], cycle[i + 1])]
    
    return (True, cycle, profit)
 
# Example usage:
currencies = ['USD', 'EUR', 'GBP', 'JPY']
rates = {
    ('USD', 'EUR'): 0.85, ('EUR', 'USD'): 1.20,
    ('EUR', 'GBP'): 0.86, ('GBP', 'EUR'): 1.17,
    ('GBP', 'USD'): 1.40, ('USD', 'GBP'): 0.72,
    ('USD', 'JPY'): 110,  ('JPY', 'USD'): 0.0091,
    ('EUR', 'JPY'): 129,  ('JPY', 'EUR'): 0.0078,
    ('GBP', 'JPY'): 150,  ('JPY', 'GBP'): 0.0067,
}
 
has_arb, cycle, profit = detect_arbitrage(currencies, rates)
if has_arb:
    print(f"Arbitrage found: {' -> '.join(cycle)}")
    print(f"Profit multiplier: {profit:.4f}x")

Market Efficiency

Difference Constraints — Another Powerful Application

Bellman-Ford has a beautiful theoretical application: solving systems of difference constraints.

What are difference constraints?

A system of difference constraints is a set of inequalities of the form:

xᵢ - xⱼ ≤ cᵢⱼ

where xᵢ and xⱼ are variables and cᵢⱼ is a constant.

Example system:

x₁ - x₂ ≤ 3
x₂ - x₃ ≤ -1
x₃ - x₁ ≤ 5

The graph transformation:

For each constraint xᵢ - xⱼ ≤ c, create an edge j → i with weight c.

Why? If we find shortest path distances d[i], they satisfy:

d[i] ≤ d[j] + c (the relaxation condition)
Which rearranges to: d[i] - d[j] ≤ c

This is exactly our constraint! The shortest path distances are a solution to the constraint system.

What negative cycles mean for constraints:

If the constraint graph has a negative cycle, the system is unsatisfiable. Why?

A negative cycle through vertices v₁, v₂, ..., vₖ, v₁ corresponds to constraints:

xᵥ₂ - xᵥ₁ ≤ c₁
xᵥ₃ - xᵥ₂ ≤ c₂
...
xᵥ₁ - xᵥₖ ≤ cₖ

Adding all constraints: (xᵥ₂ - xᵥ₁) + (xᵥ₃ - xᵥ₂) + ... + (xᵥ₁ - xᵥₖ) ≤ c₁ + c₂ + ... + cₖ

Left side telescopes to 0: 0 ≤ c₁ + c₂ + ... + cₖ

But if c₁ + c₂ + ... + cₖ < 0 (negative cycle), we get: 0 ≤ (negative number)

Contradiction! The system has no solution.

Bellman-Ford tells us:

No negative cycle → Solution exists (shortest path distances are a valid assignment)
Negative cycle → No solution exists

Scheduling Applications

Summary: The Power of Cycle Detection

We've thoroughly explored Bellman-Ford's negative cycle detection capability:

Key Takeaways

•Negative cycles make shortest paths undefined — Traversing a negative cycle infinitely yields arbitrarily negative path lengths.
•The V-th iteration detects cycles — If any edge can still be relaxed after V-1 iterations, a negative cycle exists.
•Finding affected vertices requires propagation — Run V additional iterations to identify all vertices reachable from negative cycles.
•Cycle reconstruction traces predecessors — Following predecessor pointers V times from an affected vertex lands on the actual cycle.
•Currency arbitrage is the classic application — Negative cycles in rate graphs represent profitable trading opportunities.
•Difference constraints connect to satisfiability — Negative cycles correspond to unsatisfiable constraint systems.

What's Next:

Page Complete