Bellman-Ford Algorithm

def bellman_ford(n, edges, src):
    """
    Find shortest paths from src to all vertices
    n: number of vertices (0-indexed)
    edges: list of (u, v, weight)
    src: source vertex
    Returns: distance array or None if negative cycle exists
    """
    # Initialize distances
    dist = [float('inf')] * n
    dist[src] = 0

    # Relax all edges V-1 times
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True

        # Early termination: no updates in this iteration
        if not updated:
            break

    # Check for negative cycles (V-th iteration)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # Negative cycle detected

    return dist

def bellman_ford_with_cycle_detection(n, edges, src):
    """
    Bellman-Ford with detailed negative cycle detection
    Returns: (distances, has_negative_cycle, cycle_nodes)
    """
    dist = [float('inf')] * n
    dist[src] = 0
    parent = [-1] * n

    # Relax edges V-1 times
    for i in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    # Check for negative cycle and track affected nodes
    negative_cycle_node = -1
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u
            negative_cycle_node = v

    if negative_cycle_node == -1:
        return dist, False, []

    # Extract negative cycle
    cycle = []
    visited = set()
    current = negative_cycle_node

    # Walk back to find cycle
    for _ in range(n):
        current = parent[current]

    # Now current is definitely in the cycle
    cycle_start = current
    while True:
        cycle.append(current)
        current = parent[current]
        if current == cycle_start:
            cycle.append(current)
            break

    cycle.reverse()
    return dist, True, cycle

def bellman_ford_k_edges(n, edges, src, dst, k):
    """
    Find shortest path using at most k edges
    Useful for problems like "Cheapest Flights Within K Stops"
    """
    # dist[i] = shortest distance to vertex i
    dist = [float('inf')] * n
    dist[src] = 0

    # Relax edges exactly k times (at most k edges)
    for iteration in range(k):
        # Use temporary array to avoid using updated values in same iteration
        temp_dist = dist.copy()

        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < temp_dist[v]:
                temp_dist[v] = dist[u] + w

        dist = temp_dist

        # Early termination
        if iteration > 0 and dist[dst] == prev_dist:
            break
        prev_dist = dist[dst]

    return dist[dst] if dist[dst] != float('inf') else -1

from collections import deque

def spfa(n, edges, src):
    """
    Queue-optimized Bellman-Ford (SPFA)
    Average case: O(E), Worst case: O(V·E)
    Only relax edges from vertices that were updated
    """
    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v, w in edges:
        graph[u].append((v, w))

    dist = [float('inf')] * n
    dist[src] = 0

    # Queue of vertices to process
    queue = deque([src])
    in_queue = [False] * n
    in_queue[src] = True

    # Count times each vertex is added to queue
    count = [0] * n
    count[src] = 1

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

                if not in_queue[v]:
                    queue.append(v)
                    in_queue[v] = True
                    count[v] += 1

                    # Negative cycle detection
                    if count[v] >= n:
                        return None  # Negative cycle

    return dist

def bellman_ford_with_path(n, edges, src, dst):
    """
    Find shortest path and reconstruct the actual path
    Returns: (distance, path)
    """
    dist = [float('inf')] * n
    dist[src] = 0
    parent = [-1] * n

    # Relax edges V-1 times
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u
                updated = True

        if not updated:
            break

    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return float('inf'), []  # Negative cycle

    # Reconstruct path
    if dist[dst] == float('inf'):
        return float('inf'), []

    path = []
    current = dst
    while current != -1:
        path.append(current)
        current = parent[current]

    path.reverse()
    return dist[dst], path

import math

def detect_arbitrage(n, exchange_rates):
    """
    Detect arbitrage opportunity in currency exchange
    exchange_rates[i][j] = rate from currency i to currency j
    Returns: True if arbitrage exists, False otherwise
    """
    # Convert to logarithmic weights
    # If product of rates > 1, arbitrage exists
    # Take negative log to use Bellman-Ford for negative cycles
    edges = []
    for u in range(n):
        for v in range(n):
            if u != v and exchange_rates[u][v] > 0:
                # Negative log to convert product to sum
                weight = -math.log(exchange_rates[u][v])
                edges.append((u, v, weight))

    # Run Bellman-Ford from any source
    dist = [float('inf')] * n
    dist[0] = 0

    # Relax edges V-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycle (arbitrage)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True  # Arbitrage detected

    return False

Shortest Path Algorithm Selection:

1. Does graph have negative edge weights?
   ├── YES → Continue to 2
   │   ├── Single-source? → Use Bellman-Ford
   │   ├── All-pairs? → Use Floyd-Warshall
   │   └── Need cycle detection? → Use Bellman-Ford
   │
   └── NO → Continue to 3

2. Single-source or all-pairs?
   ├── Single-source → Use Dijkstra
   │   └── Very sparse graph? → Consider SPFA
   │
   └── All-pairs → Continue to 4

3. What's the graph size?
   ├── Small (V ≤ 400) → Floyd-Warshall
   └── Large → Run Dijkstra V times

4. Special considerations:
   ├── Need to detect negative cycles? → Bellman-Ford or Floyd-Warshall
   ├── Edge count constraint (K edges)? → Modified Bellman-Ford
   ├── Unweighted graph? → BFS
   └── Tree structure? → DFS/BFS

// LC 787 - Cheapest Flights Within K Stops
// IDEA: Bellman-Ford — relax edges k+1 times; copy dist array each iteration
// time = O(K * E), space = O(N)
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    for (int i = 0; i <= k; i++) {
        int[] tmp = Arrays.copyOf(dist, n);
        for (int[] f : flights) {
            if (dist[f[0]] != Integer.MAX_VALUE)
                tmp[f[1]] = Math.min(tmp[f[1]], dist[f[0]] + f[2]);
        }
        dist = tmp;
    }
    return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}

# LC 787 - Cheapest Flights Within K Stops
# Classic Bellman-Ford with K edges constraint

def findCheapestPrice(n, flights, src, dst, k):
    """
    Find cheapest price with at most k stops (k+1 edges)
    """
    # Initialize distances
    prices = [float('inf')] * n
    prices[src] = 0

    # Relax edges at most k+1 times (k stops = k+1 edges)
    for i in range(k + 1):
        # Use temp array to ensure we only use distances from previous iteration
        temp_prices = prices.copy()

        for u, v, price in flights:
            if prices[u] != float('inf'):
                temp_prices[v] = min(temp_prices[v], prices[u] + price)

        prices = temp_prices

    return prices[dst] if prices[dst] != float('inf') else -1


# Alternative: SPFA with stops tracking
def findCheapestPrice_SPFA(n, flights, src, dst, k):
    """
    SPFA variant with stops tracking
    """
    from collections import deque

    # Build adjacency list
    graph = [[] for _ in range(n)]
    for u, v, price in flights:
        graph[u].append((v, price))

    # (cost, node, stops)
    queue = deque([(0, src, 0)])
    # best_cost[node] = minimum cost to reach node
    best = {src: 0}

    min_cost = float('inf')

    while queue:
        cost, node, stops = queue.popleft()

        # Reached destination
        if node == dst:
            min_cost = min(min_cost, cost)
            continue

        # Exceeded stops limit
        if stops > k:
            continue

        # Explore neighbors
        for neighbor, price in graph[node]:
            new_cost = cost + price

            # Pruning: only continue if this is a better path
            if new_cost < best.get(neighbor, float('inf')) or new_cost < min_cost:
                best[neighbor] = new_cost
                queue.append((new_cost, neighbor, stops + 1))

    return min_cost if min_cost != float('inf') else -1

dp[t][v] = min( dp[t-1][v],                                  <-- carry-over => "at most t edges"
                min over each edge (u -> v, w) of dp[t-1][u] + w )

dp[0][src] = 0, dp[0][*] = INF
answer     = dp[k+1][dst]        # k stops == k+1 edges

// java
// LC 787 - Cheapest Flights Within K Stops
// IDEA: layered DP form of Bellman-Ford — dp[t][v] = cheapest cost to reach v using at most t edges
// time = O(K * E), space = O(K * N) for the full table (O(N) if you keep only 2 rows)
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    final int INF = Integer.MAX_VALUE / 2;          // /2 so dp[u] + w never overflows
    int[][] dp = new int[k + 2][n];
    Arrays.fill(dp[0], INF);
    dp[0][src] = 0;

    for (int t = 1; t <= k + 1; t++) {
        dp[t] = dp[t - 1].clone();                  // carry-over => "AT MOST t edges"
        for (int[] f : flights) {
            if (dp[t - 1][f[0]] < INF)
                dp[t][f[1]] = Math.min(dp[t][f[1]], dp[t - 1][f[0]] + f[2]);
        }
    }
    return dp[k + 1][dst] >= INF ? -1 : dp[k + 1][dst];
}

// Variant: shortest path using EXACTLY k edges — just drop the carry-over row
// time = O(K * E), space = O(N)
public int cheapestExactlyKEdges(int n, int[][] edges, int src, int dst, int k) {
    final int INF = Integer.MAX_VALUE / 2;
    int[] prev = new int[n];
    Arrays.fill(prev, INF);
    prev[src] = 0;
    for (int t = 0; t < k; t++) {
        int[] cur = new int[n];
        Arrays.fill(cur, INF);                      // NO carry-over => "EXACTLY k edges"
        for (int[] e : edges) {
            if (prev[e[0]] < INF)
                cur[e[1]] = Math.min(cur[e[1]], prev[e[0]] + e[2]);
        }
        prev = cur;
    }
    return prev[dst] >= INF ? -1 : prev[dst];
}

# python
# LC 787 - Cheapest Flights Within K Stops
# IDEA: layered DP form of Bellman-Ford — dp[t][v] = cheapest cost to reach v using at most t edges
# time = O(K * E), space = O(K * N) for the full table (O(N) if you keep only 2 rows)
def findCheapestPrice(n, flights, src, dst, k):
    INF = float('inf')
    dp = [[INF] * n for _ in range(k + 2)]
    dp[0][src] = 0

    for t in range(1, k + 2):
        dp[t] = dp[t - 1][:]                    # carry-over => "AT MOST t edges"
        for u, v, w in flights:
            if dp[t - 1][u] != INF:
                dp[t][v] = min(dp[t][v], dp[t - 1][u] + w)

    return -1 if dp[k + 1][dst] == INF else dp[k + 1][dst]


# Variant: shortest path using EXACTLY k edges — just drop the carry-over row
# time = O(K * E), space = O(N)
def cheapest_exactly_k_edges(n, edges, src, dst, k):
    INF = float('inf')
    prev = [INF] * n
    prev[src] = 0
    for _ in range(k):
        cur = [INF] * n                         # NO carry-over => "EXACTLY k edges"
        for u, v, w in edges:
            if prev[u] != INF:
                cur[v] = min(cur[v], prev[u] + w)
        prev = cur
    return -1 if prev[dst] == INF else prev[dst]

// LC 743 - Network Delay Time
// IDEA: Bellman-Ford — relax all edges N-1 times; answer = max dist, -1 if any unreachable
// time = O(N * E), space = O(N)
public int networkDelayTime(int[][] times, int n, int k) {
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    for (int i = 0; i < n - 1; i++)
        for (int[] t : times)
            if (dist[t[0]] != Integer.MAX_VALUE)
                dist[t[1]] = Math.min(dist[t[1]], dist[t[0]] + t[2]);
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        max = Math.max(max, dist[i]);
    }
    return max;
}

# LC 743 - Network Delay Time
# Can use Bellman-Ford but Dijkstra is more efficient

def networkDelayTime(times, n, k):
    """
    Bellman-Ford approach (Dijkstra is better for this problem)
    """
    # Initialize distances (1-indexed)
    dist = [float('inf')] * (n + 1)
    dist[k] = 0

    # Relax edges n-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in times:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True

        if not updated:
            break

    # Find maximum delay
    max_delay = max(dist[1:])
    return max_delay if max_delay != float('inf') else -1

# Detect arbitrage opportunity in currency exchange
import math

def detect_arbitrage_opportunity(rates):
    """
    rates: 2D array where rates[i][j] = exchange rate from currency i to j
    Returns: True if arbitrage exists

    Example:
    rates = [
        [1, 0.5, 2.0],    # Currency 0: 1->1, 0.5->1, 2.0->2
        [2.0, 1, 0.25],   # Currency 1
        [0.5, 4.0, 1]     # Currency 2
    ]
    If 0 -> 1 -> 2 -> 0 gives > 1, arbitrage exists
    """
    n = len(rates)

    # Convert to negative log weights
    edges = []
    for i in range(n):
        for j in range(n):
            if i != j and rates[i][j] > 0:
                # -log(rate): if product > 1, sum of -logs < 0
                weight = -math.log(rates[i][j])
                edges.append((i, j, weight))

    # Bellman-Ford from any starting currency
    dist = [float('inf')] * n
    dist[0] = 0

    # Relax edges n-1 times
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycle (arbitrage)
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return True

    return False


# Example usage
def find_arbitrage_path(rates):
    """
    Not only detect but find the arbitrage path
    """
    n = len(rates)
    edges = []

    for i in range(n):
        for j in range(n):
            if i != j and rates[i][j] > 0:
                weight = -math.log(rates[i][j])
                edges.append((i, j, weight))

    dist = [0] * n  # Start with 0 (log(1) = 0)
    parent = [-1] * n

    # Relax edges
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                parent[v] = u

    # Find node in negative cycle
    cycle_node = -1
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            cycle_node = v
            parent[v] = u
            break

    if cycle_node == -1:
        return None  # No arbitrage

    # Extract cycle
    visited = set()
    current = cycle_node
    while current not in visited:
        visited.add(current)
        current = parent[current]

    # Build cycle path
    path = [current]
    node = parent[current]
    while node != current:
        path.append(node)
        node = parent[node]
    path.reverse()

    return path

def min_cost_with_discounts(n, roads, src, dst, discounts):
    """
    Find minimum cost where some roads have discounts (negative weights)
    roads: [(u, v, cost)]
    discounts: {(u, v): discount_amount}
    """
    # Apply discounts to create edges with potentially negative weights
    edges = []
    for u, v, cost in roads:
        actual_cost = cost - discounts.get((u, v), 0)
        edges.append((u, v, actual_cost))
        # If undirected
        actual_cost_rev = cost - discounts.get((v, u), 0)
        edges.append((v, u, actual_cost_rev))

    # Bellman-Ford
    dist = [float('inf')] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # Check for negative cycle
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return "Infinite arbitrage possible"

    return dist[dst] if dist[dst] != float('inf') else -1

def shortest_path_with_time_machine(n, edges, src, dst):
    """
    Some edges go back in time (negative weight)
    Need to detect if infinite time travel loop exists

    edges: [(u, v, time_delta)]  # negative = go back in time
    """
    dist = [float('inf')] * n
    dist[src] = 0
    parent = [-1] * n

    # Bellman-Ford
    for _ in range(n - 1):
        for u, v, time in edges:
            if dist[u] != float('inf') and dist[u] + time < dist[v]:
                dist[v] = dist[u] + time
                parent[v] = u

    # Check if destination is affected by negative cycle
    affected = set()
    for u, v, time in edges:
        if dist[u] != float('inf') and dist[u] + time < dist[v]:
            # Mark all reachable nodes from v as affected
            affected.add(v)
            # BFS/DFS to find all reachable from v
            queue = [v]
            visited = {v}
            while queue:
                node = queue.pop(0)
                for u2, v2, _ in edges:
                    if u2 == node and v2 not in visited:
                        visited.add(v2)
                        queue.append(v2)
            affected.update(visited)

    if dst in affected:
        return "Can arrive arbitrarily early (time loop)"

    return dist[dst] if dist[dst] != float('inf') else "Unreachable"

# Bellman-Ford Implementation Checklist:

# 1. Initialize distances
dist = [float('inf')] * n
dist[src] = 0

# 2. Relax all edges V-1 times
for iteration in range(n - 1):
    updated = False
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            updated = True

    # Early termination optimization
    if not updated:
        break

# 3. Check for negative cycles (V-th iteration)
has_negative_cycle = False
for u, v, w in edges:
    if dist[u] != float('inf') and dist[u] + w < dist[v]:
        has_negative_cycle = True
        break

# 4. Handle results
if has_negative_cycle:
    return None  # or handle appropriately
return dist

# Standard Bellman-Ford Pattern
dist[src] = 0
for _ in range(V - 1):                    # V-1 iterations
    for each edge (u, v, w):              # All edges
        if dist[u] + w < dist[v]:         # Relaxation
            dist[v] = dist[u] + w

# Negative cycle check
for each edge (u, v, w):
    if dist[u] + w < dist[v]:
        return "Negative cycle exists"

# After V-1 iterations, one more check
for u, v, w in edges:
    if dist[u] + w < dist[v]:
        return "Has negative cycle"

# Use temp array to ensure using previous iteration values
for _ in range(k):
    temp = dist.copy()
    for u, v, w in edges:
        temp[v] = min(temp[v], dist[u] + w)
    dist = temp

parent = [-1] * n
# During relaxation:
if dist[u] + w < dist[v]:
    dist[v] = dist[u] + w
    parent[v] = u

# Reconstruct path
path = []
while current != -1:
    path.append(current)
    current = parent[current]
path.reverse()

# Convert multiplicative to additive
weight = -math.log(exchange_rate)
# Negative cycle = arbitrage opportunity

for _ in range(n - 1):
    updated = False
    for u, v, w in edges:
        if relax(u, v, w):
            updated = True
    if not updated:
        break  # No more updates possible