Dijkstra's Algorithm: The Complete Guide to Shortest Path Finding

Introduction

Dijkstra's Algorithm is one of the most fundamental and widely used algorithms in computer science. Named after its inventor, Dutch computer scientist Edsger W. Dijkstra, this algorithm solves the Single-Source Shortest Path problem for a graph with non-negative edge weights.

Given a source node, the algorithm finds the shortest path from that node to every other node in the graph. It is the backbone of GPS navigation systems, network routing protocols (like OSPF), and social network analysis.

Core Concepts

1. Weighted Graphs

Unlike unweighted graphs where every edge has the same value (usually 1), Dijkstra's algorithm operates on weighted graphs. Each edge has a cost (weight) associated with it, representing the "distance" or "time" required to traverse that edge.

2. Non-Negative Weights

A critical constraint of Dijkstra's algorithm is that edge weights must be non-negative (greater than or equal to zero). If the graph contains negative weights, the algorithm fails to produce the correct shortest path. For graphs with negative weights, the Bellman-Ford algorithm is the standard solution.

3. Greedy Approach

Dijkstra's algorithm is a greedy algorithm. At each step, it makes the locally optimal choice with the hope of finding a global optimum. Specifically, it always expands the node that is currently the closest to the source node.

How It Works

The algorithm maintains a set of "tentative" distances for all nodes. Initially, the distance to the source node is 0, and the distance to all other nodes is infinity. It uses a Priority Queue (Min-Heap) to efficiently retrieve the node with the smallest tentative distance.

Step-by-Step Process

1. Initialization:

• Create a distance map. Set the distance to the source node as 0 and all other nodes as Infinity.
• Create a set of visited nodes (or simply mark nodes as processed).
• Insert the source node into the Priority Queue with distance 0.

1. Processing Loop:

• While the Priority Queue is not empty:
• Extract Minimum: Remove the node with the smallest distance from the queue. If this node has already been visited, skip it.
• Mark Visited: Mark this node as visited.
• Relaxation: For each neighbor of the current node:
• Calculate the new distance: current_distance + edge_weight.
• If this new distance is smaller than the currently known distance to the neighbor, update the neighbor's distance.
• If the distance was updated, add the neighbor to the Priority Queue.

Visual Example

Consider a graph where Node A is the source:

• A -> B (cost 4)
• A -> C (cost 2)
• C -> B (cost 1)
• B -> D (cost 1)

1. Start at A (Dist: 0).
2. Neighbors B (4) and C (2). Queue: [B(4), C(2)].
3. Pop C (Dist: 2). Neighbors: B (2+1=3 < 4). Update B to 3. Queue: [B(3)].
4. Pop B (Dist: 3). Neighbors: D (3+1=4). Update D to 4. Queue: [D(4)].
5. Pop D (Dist: 4). Done.

Result: Shortest path A -> C -> B -> D (Total cost 4).

Implementation in TypeScript

Below is a robust TypeScript implementation using an Adjacency List and a Min-Heap Priority Queue.

// 1. Define the Graph Structure
type WeightedAdjacencyList = Map<string, { node: string; weight: number }[]>;

// 2. Priority Queue Implementation (Min-Heap)
class PriorityQueue {
  private heap: { node: string; priority: number }[] = [];

  enqueue(node: string, priority: number): void {
    this.heap.push({ node, priority });
    this.bubbleUp(this.heap.length - 1);
  }

  dequeue(): { node: string; priority: number } | undefined {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end) {
      this.heap[0] = end;
      this.sinkDown(0);
    }
    return min;
  }

  isEmpty(): boolean {
    return this.heap.length === 0;
  }

  private bubbleUp(n: number): void {
    const element = this.heap[n];
    while (n > 0) {
      const parentN = Math.floor((n + 1) / 2) - 1;
      const parent = this.heap[parentN];
      if (element.priority >= parent.priority) break;
      this.heap[parentN] = element;
      this.heap[n] = parent;
      n = parentN;
    }
  }

  private sinkDown(n: number): void {
    const length = this.heap.length;
    const element = this.heap[n];

    while (true) {
      const child2N = (n + 1) * 2;
      const child1N = child2N - 1;
      let swap: number | null = null;
      let child1: { node: string; priority: number } | undefined;
      let child2: { node: string; priority: number } | undefined;

      if (child1N < length) {
        child1 = this.heap[child1N];
        if (child1.priority < element.priority) {
          swap = child1N;
        }
      }

      if (child2N < length) {
        child2 = this.heap[child2N];
        if (
          (swap === null && child2.priority < element.priority) ||
          (swap !== null && child2.priority < child1!.priority)
        ) {
          swap = child2N;
        }
      }

      if (swap === null) break;
      this.heap[n] = this.heap[swap];
      this.heap[swap] = element;
      n = swap;
    }
  }
}

// 3. Dijkstra's Algorithm
function dijkstra(graph: WeightedAdjacencyList, startNode: string): Map<string, number> {
  const distances = new Map<string, number>();
  const pq = new PriorityQueue();

  // Initialize distances
  for (const node of graph.keys()) {
    distances.set(node, Infinity);
  }

  distances.set(startNode, 0);
  pq.enqueue(startNode, 0);

  while (!pq.isEmpty()) {
    const { node: current, priority: currentDistance } = pq.dequeue()!;

    // If we find a node with a distance larger than what we have recorded, skip it
    if (currentDistance > distances.get(current)!) {
      continue;
    }

    // Get neighbors
    const neighbors = graph.get(current) || [];
    for (const neighbor of neighbors) {
      const newDist = currentDistance + neighbor.weight;

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

  return distances;
}

// Usage Example
const graph: WeightedAdjacencyList = new Map([
  [
    'A',
    [
      { node: 'B', weight: 4 },
      { node: 'C', weight: 2 },
    ],
  ],
  [
    'B',
    [
      { node: 'D', weight: 1 },
      { node: 'A', weight: 4 },
    ],
  ],
  [
    'C',
    [
      { node: 'A', weight: 2 },
      { node: 'B', weight: 1 },
      { node: 'D', weight: 5 },
    ],
  ],
  [
    'D',
    [
      { node: 'B', weight: 1 },
      { node: 'C', weight: 5 },
    ],
  ],
]);

const results = dijkstra(graph, 'A');
console.log(results);
// Output: Map { 'A' => 0, 'B' => 3, 'C' => 2, 'D' => 4 }

Complexity Analysis

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

• V (Vertices): The number of nodes in the graph.
• E (Edges): The number of connections in the graph.
• Explanation: Each vertex is processed once, and each edge is examined once. However, extracting the minimum from the Priority Queue takes O(log V) time. Since we use a Min-Heap, the total time complexity is dominated by the heap operations.

Space Complexity: O(V)

• Explanation: We need to store the distance map for all vertices and the Priority Queue, which in the worst case holds all vertices.

Common Variations and Extensions

1. A* (A-Star) Algorithm

A is an extension of Dijkstra's algorithm. It uses a heuristic function to estimate the cost from the current node to the goal. This makes A significantly faster for pathfinding in large spaces (like maps) because it prioritizes nodes closer to the destination, ignoring nodes that are clearly moving away.

2. Dijkstra with Priority Queue vs. Array

While using a Priority Queue is optimal, a naive implementation might use an unsorted array to find the minimum distance node, resulting in O(V^2) time complexity. This is acceptable for very dense graphs with few vertices but inefficient for sparse graphs.

Real-World Applications

1. GPS and Navigation: Google Maps and Waze use pathfinding algorithms (often variations of Dijkstra or A*) to calculate the fastest route between two points.
2. Network Routing: The OSPF (Open Shortest Path First) protocol uses Dijkstra's algorithm to determine the most efficient path for data packets to travel across a network.
3. Social Networks: Finding the "degrees of separation" between users or finding the shortest path to a specific influencer.
4. Robotics: Path planning for robots in a warehouse or on a map.

Common Mistakes to Avoid

1. Ignoring Non-Negative Weights: Forgetting that Dijkstra's fails with negative weights. Always check your graph data.
2. Incorrect Priority Queue: Using a Max-Heap instead of a Min-Heap will cause the algorithm to process nodes in the wrong order.
3. Relaxation Logic: Forgetting to update the distance of the neighbor before pushing it to the queue, or pushing the same neighbor multiple times with outdated distances.
4. Visited Set: While not strictly necessary if you check if (currentDistance > distances.get(current)), explicitly tracking visited nodes can save time in certain implementations.

Practice Problems

To master Dijkstra's algorithm, try these LeetCode problems:

1. 743. Network Delay Time: Find the time it takes for all nodes to receive the signal.
2. 1514. Path with Maximum Probability: Find the path with the highest probability of success.
3. 1631. Path With Minimum Effort: Find the minimum effort path (using Dijkstra on edge weights).
4. 1775. Equal Sum Arrays With Minimum Number of Operations: (Uses Dijkstra to find the minimum cost to balance two arrays).

Summary

Dijkstra's Algorithm is a powerful tool for solving shortest path problems. By understanding the greedy nature of the algorithm and the importance of the Priority Queue, you can efficiently solve complex routing and navigation problems. Remember the golden rule: Always relax your edges.