Bellman Ford Algorithm Negative Weights in DSA Typescript

Mental Model

We find the shortest path from one point to all others even if some paths have negative costs, by checking all paths multiple times.

Analogy: Imagine you want to find the cheapest way to travel from your home to many friends' houses. Some roads might give you discounts (negative costs). You keep checking all roads several times to make sure you found the cheapest routes.

Graph with nodes and edges:

  (A)
  /  \
-1   4
 /     \
(B)---3-->(C)

Edges have weights, some negative (-1).

Dry Run Walkthrough

Input: Graph with edges: A->B (-1), A->C (4), B->C (3), B->A (2), C->B (5); start at A

Goal: Find shortest distances from A to all nodes, handling negative weights correctly

Step 1: Initialize distances: A=0, B=∞, C=∞

Distances: A=0, B=∞, C=∞

Why: Start with zero distance to start node and infinity to others

Step 2: Relax edges first time: update B to -1 via A->B, update C to 4 via A->C then to 2 via B->C (B=-1 + 3=2)

Distances: A=0, B=-1, C=2

Why: Check all edges to find better paths from start

Step 3: Relax edges second time: no changes

Distances: A=0, B=-1, C=2

Why: Check again, no shorter paths found using updated distances

Step 4: Relax edges third time: no changes, distances stable

Distances: A=0, B=-1, C=2

Why: No further improvements, shortest paths found

Result:

Distances: A=0, B=-1, C=2

Annotated Code

DSA Typescript

class Edge {
  constructor(public from: string, public to: string, public weight: number) {}
}

class Graph {
  edges: Edge[] = [];
  vertices: Set<string> = new Set();

  addEdge(from: string, to: string, weight: number) {
    this.edges.push(new Edge(from, to, weight));
    this.vertices.add(from);
    this.vertices.add(to);
  }
}

function bellmanFord(graph: Graph, start: string): Map<string, number> | null {
  const dist = new Map<string, number>();

  // Initialize distances
  for (const v of graph.vertices) {
    dist.set(v, Infinity);
  }
  dist.set(start, 0);

  const V = graph.vertices.size;

  // Relax edges V-1 times
  for (let i = 1; i <= V - 1; i++) {
    let updated = false;
    for (const edge of graph.edges) {
      const uDist = dist.get(edge.from)!;
      const vDist = dist.get(edge.to)!;
      if (uDist !== Infinity && uDist + edge.weight < vDist) {
        dist.set(edge.to, uDist + edge.weight);
        updated = true;
      }
    }
    if (!updated) break; // No changes, stop early
  }

  // Check for negative weight cycles
  for (const edge of graph.edges) {
    const uDist = dist.get(edge.from)!;
    const vDist = dist.get(edge.to)!;
    if (uDist !== Infinity && uDist + edge.weight < vDist) {
      return null; // Negative cycle detected
    }
  }

  return dist;
}

// Driver code
const graph = new Graph();
graph.addEdge('A', 'B', -1);
graph.addEdge('A', 'C', 4);
graph.addEdge('B', 'C', 3);
graph.addEdge('B', 'A', 2);
graph.addEdge('C', 'B', 5);

const distances = bellmanFord(graph, 'A');
if (distances === null) {
  console.log('Graph contains a negative weight cycle');
} else {
  for (const [vertex, distance] of distances.entries()) {
    console.log(`${vertex}: ${distance}`);
  }
}

for (const v of graph.vertices) { dist.set(v, Infinity); } dist.set(start, 0);

Initialize all distances to infinity except start node to zero

for (let i = 1; i < V; i++) { for (const edge of graph.edges) { if (uDist !== Infinity && uDist + edge.weight < vDist) { dist.set(edge.to, uDist + edge.weight); updated = true; } } if (!updated) break; }

Relax all edges repeatedly to update shortest distances

for (const edge of graph.edges) { if (uDist !== Infinity && uDist + edge.weight < vDist) { return null; } }

Detect negative weight cycles by checking for further improvements

Output

A: 0

B: -1

C: 2

Complexity Analysis

Time: O(V * E) because we relax all edges V-1 times where V is vertices and E is edges

Space: O(V) to store distances for each vertex

vs Alternative: Unlike Dijkstra which fails with negative weights, Bellman-Ford handles them but is slower due to repeated edge checks

Edge Cases

Graph with negative weight cycle

Algorithm detects cycle and returns null

DSA Typescript

if (uDist !== Infinity && uDist + edge.weight < vDist) { return null; }

Graph with single vertex and no edges

Distance to start is zero, others infinity (none here)

DSA Typescript

for (const v of graph.vertices) { dist.set(v, Infinity); } dist.set(start, 0);

Graph with disconnected vertices

Distances to unreachable vertices remain infinity

DSA Typescript

if (uDist !== Infinity && uDist + edge.weight < vDist)

When to Use This Pattern

When you need shortest paths but edges can have negative weights, use Bellman-Ford because it handles negatives and detects cycles.

Common Mistakes

Mistake: Stopping after one pass of edge relaxation
Fix: Relax edges V-1 times to ensure shortest paths are found

Mistake: Not checking for negative weight cycles
Fix: Add a final check for further distance improvements to detect cycles

Summary

Finds shortest paths from one node to all others even with negative edge weights.

Use when graph edges can have negative weights and you need to detect negative cycles.

Keep relaxing all edges multiple times to update distances and detect cycles.