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.