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.