Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - Time & Space Complexity

Time Complexity: Dijkstra's Algorithm Single Source Shortest Path

O((V + E) log V)

Understanding Time Complexity

We want to understand how the time needed to find shortest paths grows as the graph gets bigger.

How does the algorithm's work increase when there are more points and connections?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function dijkstra(graph: Array>, source: number): number[] {
  const dist = Array(graph.length).fill(Infinity);
  dist[source] = 0;
  const visited = new Set();
  const pq = new MinPriorityQueue();
  pq.enqueue(source, 0);

  while (!pq.isEmpty()) {
    const { element: u } = pq.dequeue();
    if (visited.has(u)) continue;
    visited.add(u);

    for (const [v, weight] of graph[u]) {
      if (!visited.has(v) && dist[u] + weight < dist[v]) {
        dist[v] = dist[u] + weight;
        pq.enqueue(v, dist[v]);
      }
    }
  }
  return dist;
}
    

This code finds the shortest distance from one starting point to all others in a weighted graph using a priority queue.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs until all nodes are visited, and inside it, the for loop checks neighbors of the current node.
• How many times: The while loop runs up to V times (number of nodes), and the for loop runs for each edge connected to the current node, totaling E edges checked.

How Execution Grows With Input

As the graph grows, the number of nodes (V) and edges (E) increase, affecting how many times the loops run.

Input Size (V, E)	Approx. Operations
10 nodes, 20 edges	About 10 dequeue operations and 20 edge relaxations
100 nodes, 500 edges	About 100 dequeue operations and 500 edge relaxations
1000 nodes, 5000 edges	About 1000 dequeue operations and 5000 edge relaxations

Pattern observation: The work grows roughly with the number of nodes plus the number of edges.

Final Time Complexity

Time Complexity: O((V + E) log V)

This means the time grows with the number of nodes and edges, multiplied by the cost of managing the priority queue.

Common Mistake

[X] Wrong: "Dijkstra's algorithm always runs in simple linear time O(V + E)."

[OK] Correct: Managing the priority queue adds a logarithmic factor, so the actual time depends on log V operations for each node or edge processed.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and why using a priority queue is important for efficiency.

Self-Check

"What if we used a simple array instead of a priority queue? How would the time complexity change?"

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