Dijkstra's Algorithm Single Source Shortest Path in DSA Typescript - Build from Scratch

Dijkstra's Algorithm Single Source Shortest Path

📖 Scenario: Imagine you are a delivery driver in a city. You want to find the shortest path from your starting location to all other locations on the map. The city map is represented as a graph where intersections are nodes and roads are edges with distances.

🎯 Goal: You will build a program that uses Dijkstra's algorithm to find the shortest distance from a starting node to all other nodes in a weighted graph.

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Set a starting node for the algorithm

Implement Dijkstra's algorithm to find shortest paths

Print the shortest distances from the start node to all other nodes

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, GPS navigation, network routing, and delivery optimization.

💼 Career

Understanding Dijkstra's algorithm is essential for software engineers working with graphs, routing algorithms, and optimization problems.

1

Create the graph as an adjacency list

Create a constant called graph as a Record<string, Array<{node: string, weight: number}>> with these exact entries: 'A' connected to 'B' with weight 4 and 'C' with weight 2, 'B' connected to 'C' with weight 5 and 'D' with weight 10, 'C' connected to 'E' with weight 3, 'E' connected to 'D' with weight 4, and 'D' connected to 'F' with weight 11.

DSA Typescript

// Your code here

Hint

Use an object where keys are node names and values are arrays of objects with node and weight.

2

Set the starting node

Create a constant called startNode and set it to the string 'A'.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

// Your code here

Hint

Just create a constant with the exact name startNode and value 'A'.

3

Implement Dijkstra's algorithm

Create a function called dijkstra that takes graph and startNode as parameters and returns a Record<string, number> of shortest distances. Use a distances object to store distances, initialize all to Infinity except startNode which is 0. Use a visited set to track visited nodes. While there are unvisited nodes, pick the unvisited node with the smallest distance, update distances to neighbors if shorter paths are found, and mark the node visited. Return the distances object.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

const startNode = 'A';

// Your code here

Hint

Use a loop to pick the closest unvisited node, update neighbors, and mark visited until all nodes are visited.

4

Print the shortest distances

Call the dijkstra function with graph and startNode, store the result in shortestDistances, then print shortestDistances using console.log.

DSA Typescript

const graph: Record> = {
  'A': [{node: 'B', weight: 4}, {node: 'C', weight: 2}],
  'B': [{node: 'C', weight: 5}, {node: 'D', weight: 10}],
  'C': [{node: 'E', weight: 3}],
  'E': [{node: 'D', weight: 4}],
  'D': [{node: 'F', weight: 11}],
  'F': []
};

const startNode = 'A';

function dijkstra(graph: Record>, startNode: string): Record {
  const distances: Record = {};
  const visited = new Set();

  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[startNode] = 0;

  while (visited.size < Object.keys(graph).length) {
    let currentNode: string | null = null;
    let smallestDistance = Infinity;

    for (const node in distances) {
      if (!visited.has(node) && distances[node] < smallestDistance) {
        smallestDistance = distances[node];
        currentNode = node;
      }
    }

    if (currentNode === null) {
      break;
    }

    for (const neighbor of graph[currentNode]) {
      const newDistance = distances[currentNode] + neighbor.weight;
      if (newDistance < distances[neighbor.node]) {
        distances[neighbor.node] = newDistance;
      }
    }

    visited.add(currentNode);
  }

  return distances;
}

// Your code here

Hint

Call the function and print the result exactly as shown.

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