Why Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript?

The Big Idea

Discover how computers find the fastest route for you in seconds, even in huge maps!

The Scenario

Imagine you are in a new city and want to find the shortest way to visit a friend's house from your hotel. You try to remember every street and calculate distances by hand.

The Problem

Doing this manually is slow and confusing. You might forget some streets or pick a longer path by mistake. It's easy to get lost or waste time.

The Solution

Dijkstra's Algorithm helps by automatically finding the shortest path from your starting point to all other places. It checks all routes step-by-step and picks the quickest way without missing any option.

Before vs After

✗ Before

let distances = { 'A': 0, 'B': Infinity, 'C': Infinity };
// Manually update distances for each neighbor
// Repeat for all nodes

✓ After

function dijkstra(graph, start) {
  // Automatically find shortest paths
  // Update distances using priority queue
  // Return shortest distances
}

What It Enables

This algorithm makes it easy to find the fastest route in maps, networks, or any system with connected points.

Real Life Example

GPS apps use Dijkstra's Algorithm to quickly show you the fastest way to drive, walk, or bike to your destination.

Key Takeaways

Manual pathfinding is slow and error-prone.

Dijkstra's Algorithm finds shortest paths efficiently.

It is widely used in navigation and network routing.

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