Topic Overview

Bellman-Ford Algorithm

Master Bellman-Ford algorithm for finding shortest paths in graphs with negative edge weights and detecting negative cycles.

Bellman-Ford algorithm finds shortest paths from a source vertex to all other vertices in a weighted graph, even with negative edge weights. It can also detect negative cycles.

Why This Matters in Interviews

Bellman-Ford is important because:

  • Negative weights: Handles cases where Dijkstra fails
  • Negative cycle detection: Critical for many applications
  • Algorithm understanding: Demonstrates dynamic programming approach
  • System design: Used in network routing, arbitrage detection

Interviewers use Bellman-Ford to assess your understanding of graph algorithms, your ability to handle edge cases (negative weights), and your knowledge of when to use different shortest path algorithms.

Core Concepts

  • Relaxation: Updating distances by checking if shorter path exists
  • V-1 iterations: Need V-1 passes to guarantee shortest paths
  • Negative cycle detection: Extra iteration to detect cycles
  • Dynamic programming: Builds solution incrementally
  • Works with negative weights: Unlike Dijkstra
  • Slower than Dijkstra: O(VE) vs O((V+E)log V)

Detailed Explanation

Algorithm Steps

1. Initialize distances: source = 0, all others = infinity
2. For V-1 iterations:
   For each edge (u, v) with weight w:
     If distance[u] + w < distance[v]:
       distance[v] = distance[u] + w
3. Check for negative cycles:
   For each edge (u, v) with weight w:
     If distance[u] + w < distance[v]:
       Negative cycle exists

Implementation

Basic Implementation:

class BellmanFord {
  private graph: Array<[number, number, number]>; // [from, to, weight]
  private vertices: number;
  
  constructor(graph: Array<[number, number, number]>, vertices: number) {
    this.graph = graph;
    this.vertices = vertices;
  }
  
  shortestPath(source: number): { distances: Map<number, number>; hasNegativeCycle: boolean } {
    const distances = new Map<number, number>();
    
    // Initialize distances
    for (let i = 0; i < this.vertices; i++) {
      distances.set(i, Infinity);
    }
    distances.set(source, 0);
    
    // Relax edges V-1 times
    for (let i = 0; i < this.vertices - 1; i++) {
      for (const [u, v, weight] of this.graph) {
        const distU = distances.get(u)!;
        const distV = distances.get(v)!;
        
        if (distU !== Infinity && distU + weight < distV) {
          distances.set(v, distU + weight);
        }
      }
    }
    
    // Check for negative cycles
    let hasNegativeCycle = false;
    for (const [u, v, weight] of this.graph) {
      const distU = distances.get(u)!;
      const distV = distances.get(v)!;
      
      if (distU !== Infinity && distU + weight < distV) {
        hasNegativeCycle = true;
        break;
      }
    }
    
    return { distances, hasNegativeCycle };
  }
}

// Time: O(V * E)
// Space: O(V)

With Path Reconstruction:

class BellmanFordWithPath {
  shortestPath(
    graph: Array<[number, number, number]>,
    vertices: number,
    source: number,
    target: number
  ): { distance: number; path: number[]; hasNegativeCycle: boolean } | null {
    const distances = new Map<number, number>();
    const previous = new Map<number, number | null>();
    
    // Initialize
    for (let i = 0; i < vertices; i++) {
      distances.set(i, Infinity);
      previous.set(i, null);
    }
    distances.set(source, 0);
    
    // Relax V-1 times
    for (let i = 0; i < vertices - 1; i++) {
      let updated = false;
      
      for (const [u, v, weight] of graph) {
        const distU = distances.get(u)!;
        const distV = distances.get(v)!;
        
        if (distU !== Infinity && distU + weight < distV) {
          distances.set(v, distU + weight);
          previous.set(v, u);
          updated = true;
        }
      }
      
      // Early termination if no updates
      if (!updated) break;
    }
    
    // Check for negative cycle
    for (const [u, v, weight] of graph) {
      const distU = distances.get(u)!;
      const distV = distances.get(v)!;
      
      if (distU !== Infinity && distU + weight < distV) {
        return { distance: -Infinity, path: [], hasNegativeCycle: true };
      }
    }
    
    // Reconstruct path
    if (distances.get(target) === Infinity) {
      return null; // No path
    }
    
    const path: number[] = [];
    let current: number | null = target;
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current)!;
    }
    
    return {
      distance: distances.get(target)!,
      path,
      hasNegativeCycle: false
    };
  }
}

Optimized Version (Early Termination)

function bellmanFordOptimized(
  graph: Array<[number, number, number]>,
  vertices: number,
  source: number
): Map<number, number> {
  const distances = new Map<number, number>();
  
  // Initialize
  for (let i = 0; i < vertices; i++) {
    distances.set(i, Infinity);
  }
  distances.set(source, 0);
  
  // Relax with early termination
  for (let i = 0; i < vertices - 1; i++) {
    let updated = false;
    
    for (const [u, v, weight] of graph) {
      const distU = distances.get(u)!;
      const distV = distances.get(v)!;
      
      if (distU !== Infinity && distU + weight < distV) {
        distances.set(v, distU + weight);
        updated = true;
      }
    }
    
    // Early termination if no updates
    if (!updated) break;
  }
  
  return distances;
}

Examples

Currency Arbitrage Detection

class CurrencyArbitrage {
  detectArbitrage(
    rates: Map<string, Map<string, number>> // currency -> currency -> rate
  ): boolean {
    // Convert to graph: -log(rate) as weight
    // Negative cycle = arbitrage opportunity
    const currencies = Array.from(rates.keys());
    const n = currencies.length;
    const graph: Array<[number, number, number]> = [];
    
    // Build graph with -log(rate) weights
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (i !== j && rates.get(currencies[i])?.has(currencies[j])) {
          const rate = rates.get(currencies[i])!.get(currencies[j])!;
          const weight = -Math.log(rate);
          graph.push([i, j, weight]);
        }
      }
    }
    
    // Run Bellman-Ford from each currency
    for (let source = 0; source < n; source++) {
      const { hasNegativeCycle } = new BellmanFord(graph, n).shortestPath(source);
      if (hasNegativeCycle) {
        return true; // Arbitrage found
      }
    }
    
    return false;
  }
}

Network Delay Time

function networkDelayTime(
  times: number[][], // [source, target, time]
  n: number, // number of nodes
  k: number // source node
): number {
  const distances = new Array(n + 1).fill(Infinity);
  distances[k] = 0;
  
  // Relax n-1 times
  for (let i = 0; i < n - 1; i++) {
    let updated = false;
    
    for (const [u, v, w] of times) {
      if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
        distances[v] = distances[u] + w;
        updated = true;
      }
    }
    
    if (!updated) break;
  }
  
  // Check for negative cycles
  for (const [u, v, w] of times) {
    if (distances[u] !== Infinity && distances[u] + w < distances[v]) {
      return -1; // Negative cycle
    }
  }
  
  // Find maximum distance
  const maxDist = Math.max(...distances.slice(1));
  return maxDist === Infinity ? -1 : maxDist;
}

Common Pitfalls

  • Not checking negative cycles: Algorithm may give wrong results. Fix: Always check after V-1 iterations
  • Wrong iteration count: Using V instead of V-1. Fix: Need exactly V-1 iterations
  • Not handling unreachable vertices: Returns Infinity. Fix: Check for Infinity in results
  • Inefficient: O(VE) is slower than Dijkstra. Fix: Use Dijkstra when no negative weights
  • Edge order matters: Processing edges in wrong order may need more iterations. Fix: Process all edges each iteration

Interview Questions

Beginner

Q: What is Bellman-Ford algorithm and when would you use it instead of Dijkstra?

A:

Bellman-Ford Algorithm finds shortest paths in weighted graphs, including those with negative edge weights.

Key Differences from Dijkstra:

FeatureBellman-FordDijkstra
Negative weights✅ Yes❌ No
Negative cycles✅ Detects❌ Fails
Time complexityO(V * E)O((V+E)log V)
ApproachDynamic programmingGreedy
IterationsV-1 passesPriority queue

When to use Bellman-Ford:

  • Negative edge weights: Graph has negative weights
  • Negative cycle detection: Need to detect arbitrage, cycles
  • Simple implementation: Easier than Dijkstra for some cases
  • Dense graphs: When E ≈ V², performance similar

When to use Dijkstra:

  • Non-negative weights: Much faster O((V+E)log V)
  • Sparse graphs: Better performance
  • Single source: When only need one source

Example use cases:

  • Currency exchange: Detect arbitrage (negative cycles)
  • Network routing: Handle negative costs
  • Game theory: Minimax with negative weights

Intermediate

Q: Explain how Bellman-Ford detects negative cycles. Why do we need V-1 iterations?

A:

Why V-1 Iterations:

In a graph with V vertices, the longest simple path has at most V-1 edges. After V-1 iterations of relaxation, all shortest paths should be found.

Negative Cycle Detection:

After V-1 iterations, if we can still relax an edge, it means:

  • There's a path with more than V-1 edges that's shorter
  • This is only possible if there's a negative cycle
  • The cycle allows us to keep reducing distance

Implementation:

function detectNegativeCycle(
  graph: Array<[number, number, number]>,
  vertices: number,
  source: number
): boolean {
  const distances = new Array(vertices).fill(Infinity);
  distances[source] = 0;
  
  // Relax V-1 times
  for (let i = 0; i < vertices - 1; i++) {
    for (const [u, v, weight] of graph) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
      }
    }
  }
  
  // Check for negative cycle
  for (const [u, v, weight] of graph) {
    if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
      return true; // Negative cycle detected
    }
  }
  
  return false;
}

Finding the cycle:

function findNegativeCycle(
  graph: Array<[number, number, number]>,
  vertices: number
): number[] | null {
  const distances = new Array(vertices).fill(Infinity);
  const previous = new Array(vertices).fill(-1);
  distances[0] = 0;
  
  let lastRelaxed = -1;
  
  // Relax V times (one extra to detect cycle)
  for (let i = 0; i < vertices; i++) {
    lastRelaxed = -1;
    
    for (const [u, v, weight] of graph) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        distances[v] = distances[u] + weight;
        previous[v] = u;
        lastRelaxed = v;
      }
    }
  }
  
  if (lastRelaxed === -1) {
    return null; // No negative cycle
  }
  
  // Trace back to find cycle
  const cycle: number[] = [];
  const visited = new Set<number>();
  let current = lastRelaxed;
  
  // Go back V steps to ensure we're in cycle
  for (let i = 0; i < vertices; i++) {
    current = previous[current];
  }
  
  // Now trace the cycle
  const cycleStart = current;
  do {
    cycle.push(current);
    current = previous[current];
  } while (current !== cycleStart);
  
  cycle.push(cycleStart);
  return cycle.reverse();
}

Senior

Q: Design a system to detect currency arbitrage opportunities across multiple exchanges in real-time. How do you handle dynamic rate updates and scale to thousands of currency pairs?

A:

class ArbitrageDetectionSystem {
  private graph: CurrencyGraph;
  private rateCache: RateCache;
  private updateQueue: UpdateQueue;
  private detectionEngine: DetectionEngine;
  
  constructor() {
    this.graph = new CurrencyGraph();
    this.rateCache = new RateCache();
    this.updateQueue = new UpdateQueue();
    this.detectionEngine = new DetectionEngine();
  }
  
  // Add/update exchange rate
  async updateRate(
    from: string,
    to: string,
    rate: number,
    exchange: string
  ): Promise<void> {
    // Update graph
    await this.graph.updateEdge(from, to, -Math.log(rate), exchange);
    
    // Queue for batch processing
    this.updateQueue.add({ from, to, rate, exchange, timestamp: Date.now() });
    
    // Trigger detection if significant change
    if (await this.isSignificantChange(from, to, rate)) {
      await this.detectArbitrage(from, to);
    }
  }
  
  // Detect arbitrage opportunities
  async detectArbitrage(source?: string, target?: string): Promise<ArbitrageOpportunity[]> {
    const opportunities: ArbitrageOpportunity[] = [];
    const currencies = await this.graph.getCurrencies();
    
    // Check all currency pairs or specific pair
    const pairsToCheck = source && target 
      ? [[source, target]]
      : this.generatePairs(currencies);
    
    for (const [from, to] of pairsToCheck) {
      const opportunity = await this.checkArbitrage(from, to);
      if (opportunity) {
        opportunities.push(opportunity);
      }
    }
    
    return opportunities;
  }
  
  private async checkArbitrage(from: string, to: string): Promise<ArbitrageOpportunity | null> {
    // Build graph with -log(rate) weights
    const graph = await this.buildGraph();
    const currencies = Array.from(graph.keys());
    const fromIdx = currencies.indexOf(from);
    const toIdx = currencies.indexOf(to);
    
    // Run Bellman-Ford
    const result = this.bellmanFord(graph, currencies.length, fromIdx);
    
    if (result.hasNegativeCycle) {
      // Find the cycle
      const cycle = this.findCycle(graph, fromIdx, currencies);
      
      // Calculate profit
      const profit = this.calculateProfit(cycle, currencies);
      
      if (profit > 0.001) { // Minimum profit threshold
        return {
          path: cycle,
          profit,
          timestamp: Date.now()
        };
      }
    }
    
    return null;
  }
  
  private async buildGraph(): Promise<Map<number, Array<[number, number]>>> {
    const graph = new Map<number, Array<[number, number]>>();
    const currencies = await this.graph.getCurrencies();
    
    for (let i = 0; i < currencies.length; i++) {
      graph.set(i, []);
      
      for (let j = 0; j < currencies.length; j++) {
        if (i !== j) {
          const rate = await this.graph.getBestRate(
            currencies[i],
            currencies[j]
          );
          if (rate) {
            const weight = -Math.log(rate);
            graph.get(i)!.push([j, weight]);
          }
        }
      }
    }
    
    return graph;
  }
  
  private bellmanFord(
    graph: Map<number, Array<[number, number]>>,
    vertices: number,
    source: number
  ): { distances: number[]; hasNegativeCycle: boolean } {
    const distances = new Array(vertices).fill(Infinity);
    distances[source] = 0;
    
    // Convert to edge list
    const edges: Array<[number, number, number]> = [];
    for (const [u, neighbors] of graph.entries()) {
      for (const [v, weight] of neighbors) {
        edges.push([u, v, weight]);
      }
    }
    
    // Relax V-1 times
    for (let i = 0; i < vertices - 1; i++) {
      for (const [u, v, weight] of edges) {
        if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
          distances[v] = distances[u] + weight;
        }
      }
    }
    
    // Check for negative cycle
    let hasNegativeCycle = false;
    for (const [u, v, weight] of edges) {
      if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
        hasNegativeCycle = true;
        break;
      }
    }
    
    return { distances, hasNegativeCycle };
  }
  
  private findCycle(
    graph: Map<number, Array<[number, number]>>,
    source: number,
    currencies: string[]
  ): string[] {
    // Implementation to find negative cycle
    // Trace back from relaxed edge
    return [];
  }
  
  private calculateProfit(cycle: string[], currencies: string[]): number {
    let profit = 1.0;
    
    for (let i = 0; i < cycle.length - 1; i++) {
      const rate = this.graph.getRate(cycle[i], cycle[i + 1]);
      profit *= rate;
    }
    
    return profit - 1.0; // Return as percentage
  }
  
  // Batch processing for efficiency
  async processUpdates(): Promise<void> {
    const updates = await this.updateQueue.getBatch(100);
    
    // Group by currency pairs
    const grouped = this.groupByPair(updates);
    
    // Process in parallel
    await Promise.all(
      Array.from(grouped.entries()).map(([pair, updates]) =>
        this.processPairUpdates(pair, updates)
      )
    );
  }
  
  private async isSignificantChange(
    from: string,
    to: string,
    newRate: number
  ): Promise<boolean> {
    const oldRate = await this.rateCache.get(from, to);
    if (!oldRate) return true;
    
    const change = Math.abs((newRate - oldRate) / oldRate);
    return change > 0.001; // 0.1% threshold
  }
}

interface ArbitrageOpportunity {
  path: string[];
  profit: number;
  timestamp: number;
}

Features:

  1. Real-time detection: Trigger on significant rate changes
  2. Batch processing: Process updates efficiently
  3. Negative cycle detection: Find arbitrage opportunities
  4. Scalability: Handle thousands of currency pairs
  5. Caching: Cache rates to avoid recomputation

Key Takeaways

  • Bellman-Ford: Finds shortest paths with negative weights
  • V-1 iterations: Need exactly V-1 passes to find all shortest paths
  • Negative cycle detection: Extra check after V-1 iterations
  • Time complexity: O(V * E) - slower than Dijkstra
  • Use when: Negative weights, need to detect cycles, simpler implementation
  • Applications: Currency arbitrage, network routing with negative costs
  • Optimization: Early termination if no updates in iteration

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.