Bellman Ford Algorithm Negative Weights in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance array with Infinity for all vertices except the source.

DSA Typescript

const distances: number[] = new Array(vertices).fill([1]);
distances[source] = 0;

Drag options to blanks, or click blank then click option'

AInfinity

B0

C-Infinity

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Setting all distances to 0, which incorrectly assumes all vertices are reachable immediately.

Using null instead of Infinity, which can cause comparison errors.

We initialize all distances to Infinity to represent that they are initially unreachable, except the source which is set to 0.

2fill in blank

medium

Complete the code to relax edges inside the main loop of Bellman-Ford.

DSA Typescript

for (let i = 0; i < vertices - 1; i++) {
  for (const [u, v, weight] of edges) {
    if (distances[u] !== Infinity && distances[u] + weight [1] distances[v]) {
      distances[v] = distances[u] + weight;
    }
  }
}

Drag options to blanks, or click blank then click option'

A>=

B>

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of <, which reverses the relaxation condition.

Using >= or <= which can cause unnecessary updates.

We relax edges when the current known distance to v is greater than the distance to u plus the edge weight.

3fill in blank

hard

Fix the error in the negative cycle detection condition.

DSA Typescript

for (const [u, v, weight] of edges) {
  if (distances[u] !== Infinity && distances[u] + weight [1] distances[v]) {
    return true; // Negative cycle detected
  }
}

Drag options to blanks, or click blank then click option'

A>=

B<

C>

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using >= or > which does not correctly detect negative cycles.

Using <= which can cause false positives.

A negative cycle exists if we can still relax an edge, meaning distances[u] + weight is less than distances[v].

4fill in blank

hard

Fill both blanks to complete the function signature and return type for Bellman-Ford.

DSA Typescript

function bellmanFord([1]: number, edges: [number, number, number][]): [2] {
  // function body
}

Drag options to blanks, or click blank then click option'

Avertices

Bnumber[]

Cedges

Dboolean

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'edges' as the first parameter name instead of 'vertices'.

Returning a boolean instead of the distances array.

The function takes the number of vertices as 'vertices' and returns an array of distances as 'number[]'.

5fill in blank

hard

Fill all three blanks to complete the edge relaxation inside the Bellman-Ford main loop.

DSA Typescript

for (let i = 0; i < [1] - 1; i++) {
  for (const [u, v, weight] of [2]) {
    if (distances[u] !== Infinity && distances[u] + weight [3] distances[v]) {
      distances[v] = distances[u] + weight;
    }
  }
}

Drag options to blanks, or click blank then click option'

Avertices

Bedges

C<

Ddistances

Attempts:

3 left

💡 Hint

Common Mistakes

Using distances instead of edges in the inner loop.

Using > instead of < in the relaxation condition.

The outer loop runs vertices - 1 times, iterating over edges, relaxing when distances[u] + weight is less than distances[v].