Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript

Mental Model

Find the shortest path from one starting point to all other points by always choosing the closest unvisited point next.

Analogy: Imagine you are in a city and want to find the shortest way to every other place. You start from your home and always go to the nearest place you haven't visited yet, updating the shortest known routes as you go.

Graph:
  (A)
 /   \
5     1
/       \
(B)---2---(C)

Distances:
A: start
B: unknown
C: unknown

Pointers:
Start at A, distances updated as we explore neighbors.

Dry Run Walkthrough

Input: Graph with nodes A, B, C and edges: A-B=5, A-C=1, B-C=2; start at A

Goal: Find shortest distances from A to B and C

Step 1: Initialize distances: A=0, B=∞, C=∞; mark all unvisited

Distances: A=0, B=∞, C=∞; Unvisited: {A, B, C}

Why: We start knowing distance to start node is zero and others unknown

Step 2: Visit node A (closest unvisited), update neighbors B and C distances

Distances: A=0, B=5, C=1; Unvisited: {B, C}

Why: From A, we can reach B with cost 5 and C with cost 1, update distances

Step 3: Visit node C (closest unvisited), update neighbor B distance if shorter

Distances: A=0, B=3, C=1; Unvisited: {B}

Why: From C, path to B is 1 + 2 = 3 which is shorter than previous 5, update B

Step 4: Visit node B (last unvisited), no neighbors to update

Distances: A=0, B=3, C=1; Unvisited: {}

Why: All nodes visited, shortest distances found

Result:

Distances: A=0 -> B=3 -> C=1

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<string, Array<{node: string; weight: number}>> = new Map();

  addEdge(u: string, v: string, w: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push({node: v, weight: w});
    this.adjacencyList.get(v)!.push({node: u, weight: w});
  }
}

function dijkstra(graph: Graph, start: string): Map<string, number> {
  const distances = new Map<string, number>();
  const visited = new Set<string>();
  const nodes = Array.from(graph.adjacencyList.keys());

  // Initialize distances
  for (const node of nodes) {
    distances.set(node, Infinity);
  }
  distances.set(start, 0);

  while (visited.size < nodes.length) {
    // Find unvisited node with smallest distance
    let currentNode: string | null = null;
    let smallestDistance = Infinity;
    for (const node of nodes) {
      if (!visited.has(node) && distances.get(node)! < smallestDistance) {
        smallestDistance = distances.get(node)!;
        currentNode = node;
      }
    }

    if (currentNode === null) break; // Remaining nodes unreachable

    visited.add(currentNode);

    // Update distances for neighbors
    for (const neighbor of graph.adjacencyList.get(currentNode)!) {
      if (!visited.has(neighbor.node)) {
        const newDist = distances.get(currentNode)! + neighbor.weight;
        if (newDist < distances.get(neighbor.node)!) {
          distances.set(neighbor.node, newDist);
        }
      }
    }
  }

  return distances;
}

// Driver code
const graph = new Graph();
graph.addEdge('A', 'B', 5);
graph.addEdge('A', 'C', 1);
graph.addEdge('B', 'C', 2);

const shortestDistances = dijkstra(graph, 'A');
for (const [node, dist] of shortestDistances) {
  console.log(`${node}: ${dist}`);
}

distances.set(start, 0);

Set distance to start node as zero

for (const node of nodes) { if (!visited.has(node) && distances.get(node)! < smallestDistance) { smallestDistance = distances.get(node)!; currentNode = node; } }

Select unvisited node with smallest known distance

visited.add(currentNode);

Mark current node as visited to avoid revisiting

for (const neighbor of graph.adjacencyList.get(currentNode)!) { if (!visited.has(neighbor.node)) { const newDist = distances.get(currentNode)! + neighbor.weight; if (newDist < distances.get(neighbor.node)!) { distances.set(neighbor.node, newDist); } } }

Update distances for neighbors if shorter path found

Output

A: 0

B: 3

C: 1

Complexity Analysis

Time: O(V^2) because for each vertex we find the closest unvisited vertex by scanning all vertices

Space: O(V + E) because we store all vertices and edges in adjacency list and distances

vs Alternative: Using a priority queue reduces time to O((V + E) log V), which is faster for large graphs

Edge Cases

Graph with disconnected nodes

Distances to unreachable nodes remain Infinity

DSA Typescript

if (currentNode === null) break; // Remaining nodes unreachable

Graph with single node

Distance to start node is zero, no neighbors to update

DSA Typescript

distances.set(start, 0);

Graph with multiple edges between same nodes

Algorithm picks the shortest edge automatically by updating distances

DSA Typescript

if (newDist < distances.get(neighbor.node)!) { distances.set(neighbor.node, newDist); }

When to Use This Pattern

When you need shortest paths from one point to all others in a weighted graph with no negative edges, use Dijkstra's algorithm because it efficiently finds minimum distances step-by-step.

Common Mistakes

Mistake: Not updating distances when a shorter path is found
Fix: Add condition to update distance only if new path is shorter

Mistake: Visiting nodes multiple times without marking visited
Fix: Use a visited set to avoid reprocessing nodes

Mistake: Assuming algorithm works with negative edge weights
Fix: Remember Dijkstra's algorithm requires all edge weights to be non-negative

Summary

Finds shortest distances from one start node to all others in a weighted graph without negative edges.

Use when you want minimum travel cost or distance from a single source to every other point.

Always pick the closest unvisited node next and update neighbors' distances to find shortest paths.

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