Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dijkstra's Algorithm on a Simple Graph

What is the shortest distance array output after running Dijkstra's algorithm from node 0?

DSA Typescript

const graph = [
  [{node:1, weight:4}, {node:2, weight:1}],
  [{node:3, weight:1}],
  [{node:1, weight:2}, {node:3, weight:5}],
  []
];

function dijkstra(graph: {node:number, weight:number}[][], start: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const visited = new Set<number>();
  while (visited.size < graph.length) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < dist.length; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    if (u === -1) break;
    visited.add(u);
    for (const edge of graph[u]) {
      if (dist[u] + edge.weight < dist[edge.node]) {
        dist[edge.node] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

console.log(dijkstra(graph, 0));

A [0, 3, 2, 5]

B [0, 4, 1, 6]

C [0, 2, 1, 3]

D [0, 3, 1, 4]

💡 Hint

Trace the shortest path updates step by step from node 0.

Starting from node 0, distances update as follows: node 2 gets distance 1, node 1 gets updated to 3 via node 2, and node 3 gets distance 4 via node 1.

🧠 Conceptual

intermediate

Understanding Dijkstra's Algorithm Behavior

Which statement correctly describes Dijkstra's algorithm behavior on graphs with negative edge weights?

A It always finds the shortest path even with negative edges.

B It may fail to find the correct shortest path if negative edges exist.

C It ignores negative edges and treats them as zero weight.

D It runs faster on graphs with negative edges.

💡 Hint

Think about how negative weights affect path cost updates.

Dijkstra's algorithm assumes all edge weights are non-negative. Negative edges can cause it to miss shorter paths.

🔧 Debug

advanced

Identify the Bug in Dijkstra's Implementation

What error will this Dijkstra's algorithm code produce when run?

DSA Typescript

function dijkstraBug(graph: {node:number, weight:number}[][], start: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const visited = new Set<number>();
  while (visited.size <= graph.length) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < dist.length; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    if (u === -1) break;
    visited.add(u);
    for (const edge of graph[u]) {
      if (dist[u] + edge.weight < dist[edge.node]) {
        dist[edge.node] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

const graph = [
  [{node:1, weight:7}],
  [{node:2, weight:5}],
  []
];
console.log(dijkstraBug(graph, 0));

A Infinite loop causing program to hang

B Returns correct shortest distances [0,7,12]

C Throws TypeError due to undefined node access

D Returns array with all Infinity values

💡 Hint

Check the loop condition carefully.

The while loop condition uses <= graph.length, causing the loop to run one extra time and never break properly, leading to an infinite loop.

🚀 Application

advanced

Choosing Data Structures for Efficient Dijkstra

Which data structure choice will optimize Dijkstra's algorithm for a graph with many nodes and edges?

A Use an adjacency list and a min-priority queue (min-heap) for selecting next node

B Use an adjacency matrix and a simple array for distances

C Use a linked list for graph edges and a stack for node selection

D Use a hash map for edges and a queue for node selection

💡 Hint

Think about how to quickly find the next closest node.

An adjacency list saves space for sparse graphs, and a min-heap efficiently selects the next node with the smallest tentative distance.

❓ Predict Output

expert

Output of Dijkstra's Algorithm with Multiple Paths

What is the shortest distance array output after running Dijkstra's algorithm from node 0 on this graph?

DSA Typescript

const graph = [
  [{node:1, weight:10}, {node:2, weight:3}],
  [{node:2, weight:1}, {node:3, weight:2}],
  [{node:1, weight:4}, {node:3, weight:8}, {node:4, weight:2}],
  [{node:4, weight:7}],
  [{node:3, weight:9}]
];

function dijkstra(graph: {node:number, weight:number}[][], start: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[start] = 0;
  const visited = new Set<number>();
  while (visited.size < graph.length) {
    let u = -1;
    let minDist = Infinity;
    for (let i = 0; i < dist.length; i++) {
      if (!visited.has(i) && dist[i] < minDist) {
        minDist = dist[i];
        u = i;
      }
    }
    if (u === -1) break;
    visited.add(u);
    for (const edge of graph[u]) {
      if (dist[u] + edge.weight < dist[edge.node]) {
        dist[edge.node] = dist[u] + edge.weight;
      }
    }
  }
  return dist;
}

console.log(dijkstra(graph, 0));

A [0, 7, 3, 5, 5]

B [0, 7, 3, 9, 5]

C [0, 10, 3, 5, 5]

D [0, 10, 3, 8, 2]

💡 Hint

Consider all possible paths and update distances carefully.

Shortest distances are: node 0=0, node 2=3, node 1=7 (via node 2), node 3=5 (via node 1), node 4=5 (via node 2).