Bellman Ford Algorithm Negative Weights in DSA Typescript - Build from Scratch

Bellman Ford Algorithm Negative Weights

📖 Scenario: You are working on a navigation system that needs to find the shortest path between cities. Some roads have toll discounts represented as negative weights. You need to handle these negative weights safely.

🎯 Goal: Build a TypeScript program that uses the Bellman Ford algorithm to find the shortest distances from a starting city to all other cities, even when some roads have negative weights.

📋 What You'll Learn

Create an array of edges representing roads with source, destination, and weight

Create a variable for the number of vertices (cities)

Implement the Bellman Ford algorithm to calculate shortest distances

Detect if there is a negative weight cycle

Print the shortest distances or a message if a negative cycle exists

💡 Why This Matters

🌍 Real World

Navigation systems and routing algorithms often need to handle roads with discounts or penalties, which can be modeled as negative weights.

💼 Career

Understanding Bellman Ford is important for software engineers working on graph algorithms, network routing, and optimization problems.

1

Create the graph edges array

Create a variable called edges as an array of objects with these exact entries: {src: 0, dest: 1, weight: 5}, {src: 1, dest: 2, weight: -2}, {src: 2, dest: 3, weight: 3}, {src: 3, dest: 1, weight: 1}, {src: 0, dest: 3, weight: 10}.

DSA Typescript

// Your code here

Hint

Use an array of objects where each object has src, dest, and weight properties.

2

Set the number of vertices

Create a variable called vertices and set it to 4 to represent the number of cities.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];
// Your code here

Hint

Count the unique cities from the edges and assign the number to vertices.

3

Implement the Bellman Ford algorithm

Create a function called bellmanFord that takes edges, vertices, and start as parameters. Inside, create a distances array of length vertices filled with Infinity. Set distances[start] to 0. Use a for loop from 0 to vertices - 1 to relax edges. Then check for negative weight cycles by iterating over edges and returning null if a cycle is found. Otherwise, return distances.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];

const vertices = 4;

// Your code here

Hint

Follow the Bellman Ford steps: initialize distances, relax edges multiple times, then check for negative cycles.

4

Print the shortest distances or negative cycle message

Call bellmanFord(edges, vertices, 0) and store the result in result. If result is null, print "Graph contains a negative weight cycle". Otherwise, print "Shortest distances from vertex 0:" followed by the result array.

DSA Typescript

const edges = [
  {src: 0, dest: 1, weight: 5},
  {src: 1, dest: 2, weight: -2},
  {src: 2, dest: 3, weight: 3},
  {src: 3, dest: 1, weight: 1},
  {src: 0, dest: 3, weight: 10}
];

const vertices = 4;

function bellmanFord(edges: {src: number; dest: number; weight: number}[], vertices: number, start: number): number[] | null {
  const distances = new Array(vertices).fill(Infinity);
  distances[start] = 0;

  for (let i = 0; i < vertices - 1; i++) {
    for (const edge of edges) {
      if (distances[edge.src] !== Infinity && distances[edge.src] + edge.weight < distances[edge.dest]) {
        distances[edge.dest] = distances[edge.src] + edge.weight;
      }
    }
  }

  for (const edge of edges) {
    if (distances[edge.src] !== Infinity && distances[edge.src] + edge.weight < distances[edge.dest]) {
      return null; // Negative weight cycle detected
    }
  }

  return distances;
}

// Your code here

Hint

Call the function with start vertex 0. Check if the result is null to detect negative cycles. Print the distances array if no cycle.

Practice

1. What is the main advantage of the Bellman-Ford algorithm compared to Dijkstra's algorithm?

easy

A. It uses less memory.

B. It runs faster on all graphs.

C. It can handle graphs with negative weight edges.

D. It only works on directed acyclic graphs.

Solution

1. Step 1: Understand the limitation of Dijkstra's algorithm

   Dijkstra's algorithm cannot correctly handle graphs with negative weight edges because it assumes that once a node's shortest path is found, it cannot be improved.

2. Step 2: Identify Bellman-Ford's capability

   Bellman-Ford algorithm can handle negative weight edges and detect negative weight cycles, making it more versatile for such graphs.

3. Final Answer:

   It can handle graphs with negative weight edges. -> Option C

4. Quick Check:

   Negative weights handled = A [OK]

Hint: Bellman-Ford works with negative edges, Dijkstra doesn't [OK]

Common Mistakes:

• Thinking Bellman-Ford is always faster
• Believing it uses less memory
• Assuming it only works on acyclic graphs

2. Which of the following is the correct TypeScript syntax to initialize the distance array for Bellman-Ford with infinity except the source node set to 0?

easy

A. const dist = new Array(n).fill(Infinity); dist[source] = 0;

B. const dist = Array(n).fill(0); dist[source] = Infinity;

C. const dist = new Array(n).fill(0); dist[source] = 0;

D. const dist = new Array(n).fill(-Infinity); dist[source] = 0;

Solution

1. Step 1: Initialize distances with Infinity

   We start with all distances as Infinity to represent unknown paths, except the source which is 0.

2. Step 2: Correct syntax for array initialization

   Using new Array(n).fill(Infinity) creates an array of size n filled with Infinity, then setting dist[source] = 0 sets the source distance correctly.

3. Final Answer:

   const dist = new Array(n).fill(Infinity); dist[source] = 0; -> Option A

4. Quick Check:

   Initialize with Infinity except source 0 = C [OK]

Hint: Fill array with Infinity, then set source to 0 [OK]

Common Mistakes:

• Filling with 0 instead of Infinity
• Setting source distance to Infinity
• Using -Infinity which is incorrect

3. Consider the following TypeScript code snippet implementing one iteration of edge relaxation in Bellman-Ford:

for (const [u, v, w] of edges) {
  if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
    dist[v] = dist[u] + w;
  }
}
console.log(dist);

If edges = [[0,1,4],[1,2,-2],[0,2,5]] and initial dist = [0, Infinity, Infinity], what will be the output after this iteration?

medium

A. [0, 4, 5]

B. [0, 5, 3]

C. [0, Infinity, Infinity]

D. [0, 4, 2]

Solution

1. Step 1: Relax edge (0,1,4)

   dist[0] = 0, 0 + 4 = 4 < dist[1] (Infinity), so dist[1] = 4.

2. Step 2: Relax edge (1,2,-2)

   dist[1] = 4, 4 + (-2) = 2 < dist[2] (Infinity), so dist[2] = 2.

3. Step 3: Relax edge (0,2,5)

   dist[0] = 0, 0 + 5 = 5 < dist[2] (2)? No, so no update.

4. Final Answer:

   [0, 4, 2] -> Option D

5. Quick Check:

   Relax edges updates dist to [0,4,2] [OK]

Hint: Relax edges in order, update dist if smaller [OK]

Common Mistakes:

• Not updating dist[2] after second edge
• Updating dist[2] incorrectly on last edge
• Ignoring initial Infinity checks

4. The following TypeScript code attempts to detect a negative weight cycle after Bellman-Ford iterations:

for (const [u, v, w] of edges) {
  if (dist[u] + w < dist[v]) {
    console.log('Negative cycle detected');
  }
}

What is the bug in this code snippet?

medium

A. It does not check if dist[u] is Infinity before comparison.

B. It should update dist[v] inside the loop.

C. It should use <= instead of < in the condition.

D. It should run inside the main relaxation loop.

Solution

1. Step 1: Understand the condition for negative cycle detection

   After all relaxation rounds, if any edge can still relax dist[v], a negative cycle exists.

2. Step 2: Identify missing Infinity check

   If dist[u] is Infinity (unreachable), dist[u] + w is invalid and can cause wrong detection or runtime error.

3. Final Answer:

   It does not check if dist[u] is Infinity before comparison. -> Option A

4. Quick Check:

   Check dist[u] !== Infinity before comparing [OK]

Hint: Always check dist[u] !== Infinity before edge relaxation [OK]

Common Mistakes:

• Forgetting to check dist[u] Infinity
• Trying to update dist[v] in detection phase
• Misplacing detection inside main loop

5. You have a graph with edges: [[0,1,1],[1,2,-1],[2,3,-1],[3,1,-1]]. Using Bellman-Ford from source 0, what will be the result after all iterations?

hard

A. Algorithm will run infinitely without detection.

B. Negative cycle detected because the cycle 1->2->3->1 sums to -3.

C. Shortest distances: [0, 1, 2, 3]

D. Shortest distances: [0, 1, 0, -1]

Solution

1. Step 1: Identify the cycle and its weight

   The cycle 1->2->3->1 has weights 1->2 (-1), 2->3 (-1), 3->1 (-1), total -3, which is negative.

2. Step 2: Bellman-Ford detects negative cycles

   After |V|-1 iterations, if any edge can still relax distances, it means a negative cycle exists.

3. Step 3: Result of running Bellman-Ford

   The algorithm will detect the negative cycle and report it instead of giving shortest distances.

4. Final Answer:

   Negative cycle detected because the cycle 1->2->3->1 sums to -3. -> Option B

5. Quick Check:

   Negative cycle sum < 0 means detection = D [OK]

Hint: Sum cycle weights; negative sum means cycle detected [OK]

Common Mistakes:

• Ignoring negative cycle and reporting distances
• Assuming algorithm runs infinitely
• Miscomputing cycle weight