Shortest Path in DAG Using Topological Order 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 dist: number[] = new Array(V).fill([1]);
dist[src] = 0;

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

A-1

B0

CInfinity

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 for all distances which incorrectly assumes all nodes are reachable immediately.

Using null which is not a number and will cause errors in calculations.

We use Infinity to represent that initially all vertices are unreachable except the source which is set to 0.

2fill in blank

medium

Complete the code to perform the topological sort using DFS.

DSA Typescript

function topoSort(u: number, visited: boolean[], stack: number[], graph: Array<Array<[number, number]>>): void {
  visited[u] = true;
  for (const [v, w] of graph[u]) {
    if (!visited[[1]]) {
      topoSort(v, visited, stack, graph);
    }
  }
  stack.push(u);
}

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

Av

Bw

Cstack

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Checking the current vertex u instead of the neighbor v.

Using the weight w as a visited index which is incorrect.

We check if the adjacent vertex v is visited before calling DFS recursively.

3fill in blank

hard

Fix the error in the relaxation step inside the shortest path calculation.

DSA Typescript

for (const [v, w] of graph[u]) {
  if (dist[u] !== Infinity && dist[u] + w [1] dist[v]) {
    dist[v] = dist[u] + w;
  }
}

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

A>=

B>

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than operator which would update distances incorrectly.

Using less than or equal which can cause unnecessary updates.

We update the distance if the new path is shorter, so we check if dist[u] + w < dist[v].

4fill in blank

hard

Fill both blanks to complete the loop that processes vertices in topological order and relaxes edges.

DSA Typescript

while (stack.length > 0) {
  const u = stack.pop()!;
  if (dist[u] !== [1]) {
    for (const [v, w] of graph[u]) {
      if (dist[u] + w [2] dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }
}

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

AInfinity

B0

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of Infinity which skips valid vertices.

Using greater than operator which breaks shortest path logic.

The distance must not be Infinity to relax edges, and relaxation happens if the new distance is less than the current.

5fill in blank

hard

Fill all three blanks to complete the function that returns shortest distances from source in a DAG.

DSA Typescript

function shortestPathDAG(V: number, graph: Array<Array<[number, number]>>, src: number): number[] {
  const dist: number[] = new Array(V).fill([1]);
  dist[src] = 0;
  const visited: boolean[] = new Array(V).fill(false);
  const stack: number[] = [];
  for (let i = 0; i < V; i++) {
    if (!visited[i]) {
      [2](i, visited, stack, graph);
    }
  }
  while (stack.length > 0) {
    const u = stack.pop()!;
    if (dist[u] !== Infinity) {
      for (const [v, w] of graph[u]) {
        if (dist[u] + w [3] dist[v]) {
          dist[v] = dist[u] + w;
        }
      }
    }
  }
  return dist;
}

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

AInfinity

BtopoSort

C<

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Not initializing distances properly.

Calling wrong function or variable for topological sort.

Using wrong comparison operator in relaxation.

Initialize distances with Infinity, call topoSort for unvisited vertices, and relax edges when the new distance is less than the current.