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).

Practice

1. What is the main purpose of Dijkstra's Algorithm in graph theory?

easy

A. To detect cycles in a graph

B. To find the minimum spanning tree of a graph

C. To find the shortest path from a single source to all other vertices

D. To sort the vertices in topological order

Solution

1. Step 1: Understand the algorithm's goal

   Dijkstra's Algorithm is designed to find the shortest distance from one starting point (source) to every other point in a graph.

2. Step 2: Compare with other graph algorithms

   Minimum spanning tree algorithms find a tree connecting all vertices with minimum total weight, cycle detection finds loops, and topological sort orders vertices. These are different tasks.

3. Final Answer:

   To find the shortest path from a single source to all other vertices -> Option C

4. Quick Check:

   Dijkstra's Algorithm = shortest paths from source [OK]

Hint: Dijkstra finds shortest paths from one start point [OK]

Common Mistakes:

• Confusing shortest path with minimum spanning tree
• Thinking it detects cycles
• Mixing it with topological sorting

2. Which of the following TypeScript code snippets correctly initializes the distance array for Dijkstra's Algorithm for a graph with 5 vertices?

easy

A. const dist: number[] = Array(5).fill(Infinity); dist[0] = 0;

B. const dist: number[] = new Array(5).map(() => 0);

C. const dist: number[] = Array(5).fill(0); dist[0] = Infinity;

D. const dist: number[] = Array(5).fill(null); dist[0] = 0;

Solution

1. Step 1: Understand initialization requirements

   Distances start as Infinity except the source vertex which is 0.

2. Step 2: Check each code snippet

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; correctly fills with Infinity and sets source distance to 0. const dist: number[] = new Array(5).map(() => 0); fills with 0 incorrectly. const dist: number[] = Array(5).fill(0); dist[0] = Infinity; fills with 0 and sets source to Infinity, wrong. const dist: number[] = Array(5).fill(null); dist[0] = 0; fills with null, which is invalid for numeric distances.

3. Final Answer:

   const dist: number[] = Array(5).fill(Infinity); dist[0] = 0; -> Option A

4. Quick Check:

   Distance array init = Infinity except source 0 [OK]

Hint: Fill array with Infinity, set source distance to 0 [OK]

Common Mistakes:

• Using map on new Array without fill (returns undefined)
• Setting all distances to 0 initially
• Using null instead of numeric values

3. Given the following TypeScript code snippet implementing Dijkstra's Algorithm on a graph with edges: 0->1 (4), 0->2 (1), 2->1 (2), what is the final distance array after running from source vertex 0?

const graph = new Map>();
graph.set(0, [[1, 4], [2, 1]]);
graph.set(1, []);
graph.set(2, [[1, 2]]);

const dist = Array(3).fill(Infinity);
dist[0] = 0;
const visited = new Set<number>();

while (visited.size < 3) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < 3; i++) {
    if (!visited.has(i) && dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  if (u === -1) break;
  visited.add(u);
  for (const [v, w] of graph.get(u) || []) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}
console.log(dist);

medium

A. [0, 6, 1]

B. [0, 4, 1]

C. [Infinity, Infinity, Infinity]

D. [0, 3, 1]

Solution

1. Step 1: Initialize distances and start from source 0

   dist = [0, Infinity, Infinity], visited = {}.

2. Step 2: Pick unvisited vertex with smallest dist and update neighbors

   Pick 0: update dist[1] = 4, dist[2] = 1. visited = {0}. Pick 2 (dist=1): update dist[1] = min(4, 1+2=3) = 3. visited = {0,2}. Pick 1 (dist=3): no neighbors. visited = {0,1,2}.

3. Final Answer:

   [0, 3, 1] -> Option D

4. Quick Check:

   Distances after updates = [0, 3, 1] [OK]

Hint: Update neighbors only if new path is shorter [OK]

Common Mistakes:

• Not updating dist[1] from 4 to 3 via vertex 2
• Picking wrong vertex with smallest distance
• Ignoring visited set causing infinite loops

4. Identify the bug in the following TypeScript code snippet implementing Dijkstra's Algorithm:

const graph = new Map>();
graph.set(0, [[1, 7], [2, 9], [5, 14]]);
graph.set(1, [[2, 10], [3, 15]]);
graph.set(2, [[3, 11], [5, 2]]);
graph.set(3, [[4, 6]]);
graph.set(4, [[5, 9]]);
graph.set(5, []);
const dist: number[] = new Array(graph.size);
dist.fill(Infinity);
dist[0] = 0;
const visited = new Set<number>();

while (visited.size < graph.size) {
  let u = -1;
  let minDist = Infinity;
  for (let i = 0; i < graph.size; i++) {
    if (!visited.has(i) && dist[i] < minDist) {
      minDist = dist[i];
      u = i;
    }
  }
  visited.add(u);
  for (const [v, w] of graph.get(u) || []) {
    if (dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w;
    }
  }
}

medium

A. dist array is not initialized before use

B. Adding vertex u to visited set before checking if u is -1

C. Using graph.size instead of graph.length in loop

D. Not updating dist[u] inside the loop

Solution

1. Step 1: Analyze the selection of vertex u

   If no unvisited vertex has finite dist, u remains -1.

2. Step 2: Check visited addition without validation

   Code adds u to visited without checking if u === -1, which can cause adding -1 and errors.

3. Final Answer:

   Adding vertex u to visited set before checking if u is -1 -> Option B

4. Quick Check:

   Check u !== -1 before visited.add(u) [OK]

Hint: Always verify selected vertex is valid before marking visited [OK]

Common Mistakes:

• Ignoring u === -1 case causing infinite loops
• Confusing graph.size with array length
• Not initializing dist array properly

5. You have a weighted graph with vertices 0 to 4 and edges: 0->1 (2), 0->2 (4), 1->2 (1), 1->3 (7), 2->4 (3), 3->4 (1). Using Dijkstra's Algorithm from source 0, what is the shortest path distance to vertex 4?

hard

A. 6

B. 7

C. 8

D. 9

Solution

1. Step 1: Calculate shortest distances step-by-step

   Start dist: [0,∞,∞,∞,∞] From 0: dist[1]=2, dist[2]=4 From 1: dist[2]=min(4,2+1=3)=3, dist[3]=2+7=9 From 2: dist[4]=3+3=6 From 3: dist[4]=min(6,9+1=10)=6

2. Step 2: Identify shortest distance to vertex 4

   Shortest distance to vertex 4 is 6 via path 0->1->2->4.

3. Final Answer:

   6 -> Option A

4. Quick Check:

   Shortest path distance to 4 = 6 [OK]

Hint: Check all paths and pick minimum sum of edge weights [OK]

Common Mistakes:

• Ignoring shorter path via vertex 2
• Adding edges incorrectly
• Assuming direct edge is always shortest