Bellman-Ford Algorithm - The Negative Edge Warrior

"Dijkstra nhanh hơn, nhưng Bellman-Ford mạnh hơn. Biết khi nào dùng cái nào là dấu hiệu của Senior." - HPN

The Limitation of Dijkstra

Dijkstra là "kiệt tác" của shortest path, NHƯNG nó có một điểm yếu chí mạng:

❌ DIJKSTRA'S ACHILLES HEEL

Dijkstra KHÔNG HOẠT ĐỘNG với đồ thị có negative weight edges.

    A ---(-2)---> B
    |             |
   (4)          (3)
    |             |
    v             v
    C ----(1)---> D

Dijkstra từ A: Khi visit B với cost -2, nó "greedy" chốt ngay.
Nhưng đường A → C → D → B có thể ngắn hơn!

Bellman-Ford ra đời để giải quyết vấn đề này.

Bellman-Ford vs Dijkstra

Tiêu chí	Dijkstra	Bellman-Ford
Time Complexity	$O((V+E)\log V)$	$O(V\times E)$
Negative edges	❌ Không hỗ trợ	✅ Hỗ trợ
Negative cycle detection	❌ Không	✅ Có
Use case	GPS, Maps (non-negative)	Finance, Arbitrage
Technique	Greedy + Priority Queue	Dynamic Programming

Core Concept: Relaxation

Bellman-Ford dựa trên nguyên lý Relaxation:

Nếu dist[u] + weight(u,v) < dist[v]:
    dist[v] = dist[u] + weight(u,v)

Key Insight:

• Đường đi ngắn nhất có tối đa V-1 cạnh (không có cycle)
• → Chỉ cần V-1 lần relaxation tất cả edges để đảm bảo tìm được shortest path

Negative Cycle Detection

Vòng thứ V: Nếu vẫn có edge được relax → Có negative cycle!

     A ---(-1)---> B
     ^             |
     |           (-1)
    (-1)           |
     |             v
     D <---(-1)--- C

Cycle: A → B → C → D → A = -1 + (-1) + (-1) + (-1) = -4
Mỗi lần đi vòng, distance GIẢM thêm 4!
→ Distance → -∞ (không có shortest path)

Real-World Application: Forex Arbitrage

💰 MONEY-MAKING USE CASE

Trong Forex trading, negative cycle = Arbitrage opportunity!

1 USD → 0.9 EUR → 130 JPY → 1.01 USD
      (×0.9)    (×144.4)   (×0.00778)
      
Cycle gain: 1.01 / 1.00 = 1% profit per cycle!

Cách áp dụng:

1. Đặt weight = -log(exchange_rate)
2. Negative cycle = Multiplication > 1 = Profit!

Implementation

Basic Bellman-Ford

from typing import List, Tuple, Optional
from dataclasses import dataclass


@dataclass
class Edge:
    u: int       # Source vertex
    v: int       # Destination vertex
    weight: int  # Edge weight (can be negative!)


def bellman_ford(
    V: int, 
    edges: List[Edge], 
    src: int
) -> Tuple[List[float], List[int], bool]:
    """
    Bellman-Ford Algorithm.
    
    Args:
        V: Number of vertices
        edges: List of edges (u, v, weight)
        src: Source vertex
    
    Returns:
        (distances, predecessors, has_negative_cycle)
        
    Time: O(V × E)
    Space: O(V)
    """
    INF = float('inf')
    dist = [INF] * V
    pred = [-1] * V
    dist[src] = 0
    
    # Phase 1: Relax all edges V-1 times
    for i in range(V - 1):
        updated = False
        for edge in edges:
            if dist[edge.u] != INF and dist[edge.u] + edge.weight < dist[edge.v]:
                dist[edge.v] = dist[edge.u] + edge.weight
                pred[edge.v] = edge.u
                updated = True
        
        # Early termination: No updates → Already converged
        if not updated:
            break
    
    # Phase 2: Check for negative cycle (V-th iteration)
    has_negative_cycle = False
    for edge in edges:
        if dist[edge.u] != INF and dist[edge.u] + edge.weight < dist[edge.v]:
            has_negative_cycle = True
            break
    
    return dist, pred, has_negative_cycle

Forex Arbitrage Detection

import math
from typing import List, Tuple, Optional


def detect_arbitrage(
    currencies: List[str],
    exchange_rates: List[List[float]]
) -> Optional[List[str]]:
    """
    Detect arbitrage opportunity in currency exchange.
    
    Args:
        currencies: ["USD", "EUR", "GBP", "JPY"]
        exchange_rates: rates[i][j] = rate to convert currency i to j
    
    Returns:
        Arbitrage cycle if found, None otherwise
    
    Example:
        currencies = ["USD", "EUR", "GBP"]
        rates = [
            [1, 0.9, 0.8],     # 1 USD = 0.9 EUR = 0.8 GBP
            [1.12, 1, 0.88],   # 1 EUR = 1.12 USD = 0.88 GBP
            [1.27, 1.14, 1]    # 1 GBP = 1.27 USD = 1.14 EUR
        ]
    """
    n = len(currencies)
    
    # Convert rates to negative log (để dùng Bellman-Ford)
    # log(a × b) = log(a) + log(b)
    # Arbitrage: product > 1 → sum of logs > 0 → sum of -logs < 0 → NEGATIVE CYCLE!
    edges = []
    for i in range(n):
        for j in range(n):
            if i != j and exchange_rates[i][j] > 0:
                # weight = -log(rate) để biến multiplication thành addition
                weight = -math.log(exchange_rates[i][j])
                edges.append(Edge(i, j, weight))
    
    # Run Bellman-Ford from each source
    for src in range(n):
        dist = [float('inf')] * n
        pred = [-1] * n
        dist[src] = 0
        
        # V-1 relaxations
        for _ in range(n - 1):
            for edge in edges:
                if dist[edge.u] + edge.weight < dist[edge.v]:
                    dist[edge.v] = dist[edge.u] + edge.weight
                    pred[edge.v] = edge.u
        
        # Check for negative cycle
        for edge in edges:
            if dist[edge.u] + edge.weight < dist[edge.v]:
                # Found negative cycle! Reconstruct it.
                cycle = []
                visited = set()
                curr = edge.v
                
                # Walk back to find a node in the cycle
                for _ in range(n):
                    curr = pred[curr]
                
                # Reconstruct cycle
                start = curr
                cycle.append(currencies[curr])
                curr = pred[curr]
                while curr != start:
                    cycle.append(currencies[curr])
                    curr = pred[curr]
                cycle.append(currencies[start])
                
                cycle.reverse()
                return cycle
    
    return None


def calculate_arbitrage_profit(
    cycle: List[str],
    currencies: List[str],
    exchange_rates: List[List[float]]
) -> float:
    """Calculate profit percentage from arbitrage cycle."""
    product = 1.0
    for i in range(len(cycle) - 1):
        from_idx = currencies.index(cycle[i])
        to_idx = currencies.index(cycle[i + 1])
        product *= exchange_rates[from_idx][to_idx]
    
    return (product - 1) * 100  # Profit percentage

Production Code

# HPN Engineering Standard
# Implementation: Bellman-Ford with all features

from typing import List, Tuple, Optional
from dataclasses import dataclass
import math


@dataclass
class Edge:
    u: int
    v: int
    weight: float


class BellmanFord:
    """
    Production-ready Bellman-Ford implementation.
    
    Features:
    - Shortest paths from single source
    - Negative cycle detection
    - Path reconstruction
    - Early termination optimization
    """
    
    def __init__(self, V: int):
        self.V = V
        self.edges: List[Edge] = []
        self.dist: List[float] = []
        self.pred: List[int] = []
        self.has_negative_cycle = False
    
    def add_edge(self, u: int, v: int, weight: float):
        """Add directed edge u → v with given weight."""
        self.edges.append(Edge(u, v, weight))
    
    def run(self, src: int) -> bool:
        """
        Run Bellman-Ford from source.
        
        Returns: True if no negative cycle, False otherwise.
        """
        INF = float('inf')
        self.dist = [INF] * self.V
        self.pred = [-1] * self.V
        self.dist[src] = 0
        
        # Phase 1: V-1 relaxations
        for i in range(self.V - 1):
            updated = False
            for edge in self.edges:
                if (self.dist[edge.u] != INF and 
                    self.dist[edge.u] + edge.weight < self.dist[edge.v]):
                    self.dist[edge.v] = self.dist[edge.u] + edge.weight
                    self.pred[edge.v] = edge.u
                    updated = True
            
            if not updated:
                break
        
        # Phase 2: Negative cycle check
        self.has_negative_cycle = False
        for edge in self.edges:
            if (self.dist[edge.u] != INF and 
                self.dist[edge.u] + edge.weight < self.dist[edge.v]):
                self.has_negative_cycle = True
                break
        
        return not self.has_negative_cycle
    
    def get_distance(self, dest: int) -> float:
        """Get shortest distance to destination."""
        return self.dist[dest]
    
    def get_path(self, dest: int) -> Optional[List[int]]:
        """Reconstruct shortest path to destination."""
        if self.dist[dest] == float('inf'):
            return None
        
        path = []
        curr = dest
        while curr != -1:
            path.append(curr)
            curr = self.pred[curr]
        
        path.reverse()
        return path
    
    def find_negative_cycle(self) -> Optional[List[int]]:
        """
        Find and return a negative cycle if exists.
        Must call run() first.
        """
        if not self.has_negative_cycle:
            return None
        
        # Find an edge that can still be relaxed
        cycle_node = -1
        for edge in self.edges:
            if (self.dist[edge.u] != float('inf') and 
                self.dist[edge.u] + edge.weight < self.dist[edge.v]):
                cycle_node = edge.v
                break
        
        if cycle_node == -1:
            return None
        
        # Walk back V times to ensure we're in the cycle
        for _ in range(self.V):
            cycle_node = self.pred[cycle_node]
        
        # Reconstruct cycle
        cycle = []
        curr = cycle_node
        while True:
            cycle.append(curr)
            curr = self.pred[curr]
            if curr == cycle_node:
                break
        
        cycle.append(cycle_node)
        cycle.reverse()
        return cycle


# ============================================
# USAGE EXAMPLE
# ============================================

if __name__ == "__main__":
    # Example 1: Basic shortest path with negative edges
    print("=== Bellman-Ford: Negative Edges ===")
    bf = BellmanFord(5)
    bf.add_edge(0, 1, -1)
    bf.add_edge(0, 2, 4)
    bf.add_edge(1, 2, 3)
    bf.add_edge(1, 3, 2)
    bf.add_edge(1, 4, 2)
    bf.add_edge(3, 2, 5)
    bf.add_edge(3, 1, 1)
    bf.add_edge(4, 3, -3)
    
    if bf.run(0):
        print("Distances from vertex 0:")
        for i in range(5):
            print(f"  → {i}: {bf.get_distance(i)}, path: {bf.get_path(i)}")
    else:
        print("Negative cycle detected!")
    
    # Example 2: Forex Arbitrage
    print("\n=== Forex Arbitrage Detection ===")
    currencies = ["USD", "EUR", "GBP", "JPY"]
    # Tạo rates có arbitrage opportunity
    rates = [
        [1, 0.9, 0.75, 110],      # USD to others
        [1.12, 1, 0.84, 122],     # EUR to others
        [1.35, 1.2, 1, 148],      # GBP to others
        [0.0091, 0.0082, 0.0068, 1]  # JPY to others
    ]
    
    cycle = detect_arbitrage(currencies, rates)
    if cycle:
        profit = calculate_arbitrage_profit(cycle, currencies, rates)
        print(f"Arbitrage found: {' → '.join(cycle)}")
        print(f"Profit per cycle: {profit:.4f}%")
    else:
        print("No arbitrage opportunity found.")

Complexity Analysis

Aspect	Complexity	Notes
Time	$O(V\times E)$	V-1 iterations, each scans all edges
Space	$O(V)$	dist[] and pred[] arrays
Best case	$O(E)$	Early termination if no updates

When to Use What?

Scenario	Algorithm	Why
Non-negative weights, sparse graph	Dijkstra	Faster: O(E log V)
Negative weights possible	Bellman-Ford	Only option that works
Need negative cycle detection	Bellman-Ford	Built-in feature
Dense graph, all-pairs	Floyd-Warshall	O(V³) simpler for dense

💡 HPN's Rule

"Dijkstra trước, Bellman-Ford khi thấy negative weight hoặc cần detect cycle."