Dijkstra's Algorithm

March 31, 2026
#dijkstra #shortest-path #graph #algorithms #data-structures #interviewing

Table of Contents

Introduction

Dijkstra’s Algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. It’s the algorithm behind GPS navigation, network routing, and any system that needs to find the cheapest path between two points.

The core idea: greedily pick the unvisited vertex with the smallest known distance, then update its neighbors’ distances. This is essentially BFS with a priority queue instead of a regular queue — the priority queue ensures we always process the closest vertex next.

You should be familiar with Graphs, Graph Representation, Heaps, and BFS before reading this.

How it works

Graph:
    A --4-- B
    |       |
    2       1
    |       |
    C --3-- D --5-- E

Find shortest paths from A:

Step 1: Start at A (dist=0). Update neighbors: B=4, C=2
Step 2: Visit C (dist=2). Update: D=2+3=5
Step 3: Visit B (dist=4). Update: D=min(5, 4+1)=5 (no change)
Step 4: Visit D (dist=5). Update: E=5+5=10
Step 5: Visit E (dist=10). Done.

Shortest distances from A: {A:0, B:4, C:2, D:5, E:10}

Implementation

function dijkstra(graph, start) {
  const dist = {};
  const prev = {};
  const pq = new MinPriorityQueue();

  for (const vertex of graph.keys()) {
    dist[vertex] = Infinity;
    prev[vertex] = null;
  }
  dist[start] = 0;
  pq.enqueue(start, 0);

  while (!pq.isEmpty()) {
    const { element: u, priority: d } = pq.dequeue();

    if (d > dist[u]) continue; // skip outdated entry

    for (const { node: v, weight } of graph.get(u) || []) {
      const newDist = dist[u] + weight;
      if (newDist < dist[v]) {
        dist[v] = newDist;
        prev[v] = u;
        pq.enqueue(v, newDist);
      }
    }
  }

  return { dist, prev };
}

// Simple min priority queue (use a proper heap in production)
class MinPriorityQueue {
  constructor() { this.items = []; }
  enqueue(element, priority) {
    this.items.push({ element, priority });
    this.items.sort((a, b) => a.priority - b.priority);
  }
  dequeue() { return this.items.shift(); }
  isEmpty() { return this.items.length === 0; }
}

// Build graph
const graph = new Map();
graph.set('A', [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }]);
graph.set('B', [{ node: 'A', weight: 4 }, { node: 'D', weight: 1 }]);
graph.set('C', [{ node: 'A', weight: 2 }, { node: 'D', weight: 3 }]);
graph.set('D', [{ node: 'B', weight: 1 }, { node: 'C', weight: 3 },
                 { node: 'E', weight: 5 }]);
graph.set('E', [{ node: 'D', weight: 5 }]);

const { dist, prev } = dijkstra(graph, 'A');
console.log(dist);  // { A: 0, B: 4, C: 2, D: 5, E: 10 }

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    prev = {v: None for v in graph}
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist, prev

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1)],
    'C': [('A', 2), ('D', 3)],
    'D': [('B', 1), ('C', 3), ('E', 5)],
    'E': [('D', 5)],
}

dist, prev = dijkstra(graph, 'A')
print(dist)  # {'A': 0, 'B': 4, 'C': 2, 'D': 5, 'E': 10}

import java.util.*;

public class Dijkstra {
    public static Map<String, Integer> dijkstra(
            Map<String, List<int[]>> graph, String[] vertices, String start) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, String> prev = new HashMap<>();

        for (String v : vertices) {
            dist.put(v, Integer.MAX_VALUE);
            prev.put(v, null);
        }
        dist.put(start, 0);

        // PQ of [distance, vertexIndex]
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, Arrays.asList(vertices).indexOf(start)});

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            String u = vertices[curr[1]];

            if (d > dist.get(u)) continue;

            for (int[] edge : graph.getOrDefault(u, Collections.emptyList())) {
                String v = vertices[edge[0]];
                int weight = edge[1];
                int newDist = dist.get(u) + weight;

                if (newDist < dist.get(v)) {
                    dist.put(v, newDist);
                    prev.put(v, u);
                    pq.offer(new int[]{newDist, edge[0]});
                }
            }
        }

        return dist;
    }
}

Reconstructing the path

The prev map tracks how we reached each vertex. Walk it backwards to get the actual path:

function getPath(prev, target) {
  const path = [];
  let current = target;

  while (current !== null) {
    path.unshift(current);
    current = prev[current];
  }

  return path;
}

const { dist, prev } = dijkstra(graph, 'A');
console.log(getPath(prev, 'E'));  // ['A', 'C', 'D', 'E'] — wait, let's check
// Actually: A(0) → B(4) → D(5) → E(10), or A(0) → C(2) → D(5) → E(10)
// Both give distance 10, prev tracks whichever was found first

Why non-negative weights only?

Dijkstra’s greedy approach assumes that once a vertex is processed, its shortest distance is final. Negative weights break this:

A --1-- B
 \      |
  5    -4
   \    |
    → C ←

Dijkstra from A: processes B(1), then C(5).
But B→C = 1 + (-4) = -3, which is shorter than 5.
Dijkstra already finalized C=5 and misses this.

Complexity analysis

Implementation Time Space
Min-heap (binary) O((V + E) log V) O(V)
Unsorted array O(V²) O(V)
Fibonacci heap O(V log V + E) O(V)

The min-heap version is the standard choice. The unsorted array version is simpler but slower — it’s better only for very dense graphs where E ≈ V².

Dijkstra vs BFS

Dijkstra BFS
Edge weights Weighted (non-negative) Unweighted (or weight = 1)
Data structure Priority queue Queue
Time O((V + E) log V) O(V + E)
Use case Weighted shortest path Unweighted shortest path

BFS is a special case of Dijkstra where all weights are 1. If your graph is unweighted, use BFS — it’s simpler and faster.

Practice problems

  1. Network Delay Time (LeetCode 743)
  2. Cheapest Flights Within K Stops (LeetCode 787)
  3. Path with Minimum Effort (LeetCode 1631)
  4. Swim in Rising Water (LeetCode 778)
  5. Shortest Path in Binary Matrix (BFS variant)
Categories
Recent Posts