Floyd Warshall All Pairs Shortest Path in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the distance matrix with the input graph.

DSA Typescript

const dist = graph.map(row => row.map(value => [1]));

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

Avalue

BInfinity

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using Infinity here will ignore the actual edge weights.

Using 0 will set all distances to zero incorrectly.

We copy the input graph values directly to initialize the distance matrix.

2fill in blank

medium

Complete the code to set the distance from each vertex to itself as zero.

DSA Typescript

for (let i = 0; i < n; i++) {
  dist[i][i] = [1];
}

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

AInfinity

B1

C-1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Setting distance to Infinity or -1 is incorrect here.

Setting distance to 1 assumes a step is needed, which is wrong.

Distance from a vertex to itself is always zero.

3fill in blank

hard

Fix the error in the nested loops to correctly iterate over all vertices.

DSA Typescript

for (let k = 0; k < n; k++) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < [1]; j++) {
      // update dist[i][j]
    }
  }
}

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

Ak

Bi

Cn

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using k or i as the limit causes incorrect iteration.

Using j as the limit is invalid because j is the loop variable.

The innermost loop must run from 0 to n to cover all vertices j.

4fill in blank

hard

Fill both blanks to update the distance matrix using the Floyd Warshall formula.

DSA Typescript

if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][k] + dist[k][j] [1] dist[i][j]) {
  dist[i][j] = dist[i][k] [2] dist[k][j];
}

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

A<

B>

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < reverses the logic.

Using subtraction instead of addition breaks the distance calculation.

We update dist[i][j] if going through k is shorter (less than current), and sum the two distances.

5fill in blank

hard

Fill all three blanks to complete the Floyd Warshall function that returns the shortest paths matrix.

DSA Typescript

function floydWarshall(graph: number[][]): number[][] {
  const n = graph.length;
  const dist = graph.map(row => row.map(value => [1]));
  for (let i = 0; i < n; i++) {
    dist[i][i] = [2];
  }
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        if (dist[i][k] !== Infinity && dist[k][j] !== Infinity && dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] [3] dist[k][j];
        }
      }
    }
  }
  return dist;
}

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

Avalue

B0

C+

DInfinity

Attempts:

3 left

💡 Hint

Common Mistakes

Using Infinity instead of graph values for initialization.

Setting self-distances to Infinity or wrong values.

Using subtraction or other operators instead of addition.

Initialize dist with graph values, set zero for self-distances, and update distances by adding through k.