Bellman Ford Algorithm Negative Weights in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Bellman-Ford on a graph with negative edge weights

What is the output distances array after running Bellman-Ford on the given graph from source 0?

DSA Typescript

type Edge = { from: number; to: number; weight: number };

function bellmanFord(edges: Edge[], vertices: number, source: number): number[] {
  const dist = Array(vertices).fill(Infinity);
  dist[source] = 0;

  for (let i = 1; i < vertices; i++) {
    for (const edge of edges) {
      if (dist[edge.from] + edge.weight < dist[edge.to]) {
        dist[edge.to] = dist[edge.from] + edge.weight;
      }
    }
  }

  return dist;
}

const edges = [
  { from: 0, to: 1, weight: 4 },
  { from: 0, to: 2, weight: 5 },
  { from: 1, to: 2, weight: -3 },
  { from: 2, to: 3, weight: 4 },
  { from: 3, to: 1, weight: -6 }
];

const result = bellmanFord(edges, 4, 0);
console.log(result);

A [0, -11, -9, -5]

B [0, Infinity, Infinity, Infinity]

C [0, -2, -5, -1]

D [0, 4, 5, 9]

💡 Hint

Remember Bellman-Ford relaxes edges up to V-1 times and handles negative weights.

The algorithm updates distances by relaxing edges repeatedly. After 3 iterations (V-1), the distances array is [0, -11, -9, -5].

🧠 Conceptual

intermediate

Detecting negative weight cycles with Bellman-Ford

Which statement correctly describes how Bellman-Ford detects a negative weight cycle?

A Bellman-Ford cannot detect negative weight cycles; it only finds shortest paths.

B If the graph has any negative edge, Bellman-Ford always detects a cycle.

C If the source vertex distance becomes negative, a negative cycle is detected.

D If after V-1 iterations, any edge can still be relaxed, a negative weight cycle exists.

💡 Hint

Think about what happens if distances keep decreasing after all relaxations.

Bellman-Ford runs V-1 iterations to relax edges. If any edge can still be relaxed after that, it means a cycle reduces path cost indefinitely, indicating a negative weight cycle.

🔧 Debug

advanced

Identify the bug in this Bellman-Ford implementation

What is the bug in the following Bellman-Ford code snippet that causes incorrect shortest path results?

DSA Typescript

function bellmanFordBug(edges: {from:number,to:number,weight:number}[], vertices:number, source:number): number[] {
  const dist = Array(vertices).fill(Infinity);
  dist[source] = 0;

  for (let i = 0; i < vertices; i++) {
    for (const edge of edges) {
      if (dist[edge.from] + edge.weight < dist[edge.to]) {
        dist[edge.to] = dist[edge.from] + edge.weight;
      }
    }
  }

  return dist;
}

A The distance array is not initialized with Infinity, causing wrong comparisons.

B The outer loop runs vertices times instead of vertices - 1 times, causing extra unnecessary iterations.

C The source distance is not set to zero before relaxation starts.

D The relaxation condition uses <= instead of <, causing infinite loops.

💡 Hint

Check how many times the algorithm should relax edges for correctness.

The Bellman-Ford algorithm should run the relaxation loop exactly V-1 times. Running it V times can cause incorrect results or unnecessary computations.

🚀 Application

advanced

Using Bellman-Ford to find shortest paths in a weighted graph with negative edges

Given a graph with edges and weights (some negative), which data structure is best to represent the graph for Bellman-Ford and why?

A Edge list, because Bellman-Ford iterates over all edges directly for relaxation.

B Adjacency matrix, because it allows quick edge weight lookup.

C Adjacency list, because it uses less memory for sparse graphs.

D Incidence matrix, because it stores vertex-edge relationships explicitly.

💡 Hint

Consider how Bellman-Ford processes edges during relaxation.

Bellman-Ford requires iterating over all edges repeatedly. An edge list directly stores edges, making iteration simple and efficient.

❓ Predict Output

expert

Output after detecting negative cycle with Bellman-Ford

What will the function return or output when a negative weight cycle is detected in the graph below?

DSA Typescript

type Edge = { from: number; to: number; weight: number };

function bellmanFordDetectCycle(edges: Edge[], vertices: number, source: number): string {
  const dist = Array(vertices).fill(Infinity);
  dist[source] = 0;

  for (let i = 1; i < vertices; i++) {
    for (const edge of edges) {
      if (dist[edge.from] + edge.weight < dist[edge.to]) {
        dist[edge.to] = dist[edge.from] + edge.weight;
      }
    }
  }

  for (const edge of edges) {
    if (dist[edge.from] + edge.weight < dist[edge.to]) {
      return "Negative cycle detected";
    }
  }

  return JSON.stringify(dist);
}

const edges = [
  { from: 0, to: 1, weight: 1 },
  { from: 1, to: 2, weight: -1 },
  { from: 2, to: 0, weight: -1 }
];

const output = bellmanFordDetectCycle(edges, 3, 0);
console.log(output);

A Throws a runtime error

B [0, Infinity, Infinity]

C "Negative cycle detected"

D [0, 1, 0]

💡 Hint

Check the final step where the algorithm tests for further relaxation after V-1 iterations.

The graph contains a cycle with total negative weight. Bellman-Ford detects this by finding an edge that can still be relaxed after V-1 iterations, returning the "Negative cycle detected" message.

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