How does Dijkstra's algorithm work on graphs?

AlgorithmsJunior~3 min read

Short answer

Dijkstra's algorithm finds the shortest paths from a single starting vertex to all others in a directed or undirected graph with non-negative edge weights. It greedily picks the vertex with the smallest current distance estimate, "fixes" its answer, and then relaxes edges, improving the estimates of its neighbors through that vertex, until every reachable vertex has been processed.

Detailed explanation

When to use it

Weighted graphs with non-negative edge weights (>= 0).
Directed and undirected graphs.
Routing tasks, minimum-cost search, distance estimation on road networks, dependency graphs, and so on.

Idea of the algorithm

We maintain an array (or dictionary) dist with the best known distances from source s to every vertex. Initially dist[s] = 0, the rest are ∞. At every step we pick the unfixed vertex u with the minimal dist[u] (using a priority queue/heap), fix it as optimal, and try to improve the distances to its neighbors (relaxation).

Initialization: dist[source] = 0, ∞ for the rest; parent[v] = null.
Put source into the priority queue keyed by dist.
While the queue is not empty: dequeue the vertex u with the minimal dist[u]. If the extracted estimate is stale, skip it.
For every edge (u → v) with weight w ≥ 0, perform relaxation: if dist[u] + w < dist[v], update dist[v] and parent[v] = u, and put v into the queue with the new priority dist[v].
After a vertex u with the minimal estimate is dequeued, its dist[u] becomes final (a greedy property that holds for non-negative weights).

Why this is correct (intuition)

Non-negative weights guarantee that going further from the vertex with the minimal known distance can never make it "cheaper".
Invariant: once a vertex is dequeued, its dist is the shortest possible distance from the source.

Complexity

With a priority queue on a binary heap and adjacency lists: O((V + E) log V).
With a plain array and no heap (finding the minimum in O(V) at each step): O(V^2), convenient for dense graphs or small V.
With a Fibonacci heap: O(E + V log V) theoretically, but harder to implement.

Data structures

dist[v], the best current distance estimate.
parent[v], the predecessor for path reconstruction.
A priority queue (min-heap) keyed by dist.

Step-by-step example

Graph (undirected for simplicity, replacing each edge with two opposite ones):

A-B (4), A-C (1)
C-B (2), C-D (4)
B-E (4), D-E (1)

Start: A. Initialization: dist[A]=0, the rest=∞.

Dequeue A (0). Relaxations: B ← 4, C ← 1. dist: A=0, B=4, C=1, D=∞, E=∞.
Dequeue C (1). Relaxations: B ← min(4, 1+2=3) → 3; D ← 1+4=5. dist: A=0, B=3, C=1, D=5, E=∞.
Dequeue B (3). Relaxations: E ← 3+4=7. dist: A=0, B=3, C=1, D=5, E=7.
Dequeue D (5). Relaxations: E ← min(7, 5+1=6) → 6. dist: A=0, B=3, C=1, D=5, E=6.
Dequeue E (6). Done. The shortest path A → E has a cost of 6: A → C → D → E.

Pseudocode

function Dijkstra(G, source):
  for each v in G.V:
    dist[v] = INF
    parent[v] = null
  dist[source] = 0

  PQ = min-priority-queue()
  PQ.push(source, 0)

  while not PQ.empty():
    (u, du) = PQ.popMin()           // the vertex with the minimal current dist
    if du > dist[u]:
      continue                      // stale entry

    for each (v, w) in G.adj[u]:    // edge u -> v with weight w
      if w < 0:
        error "Dijkstra requires non-negative weights"
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        parent[v] = u
        PQ.push(v, dist[v])

  return dist, parent

Implementation in JavaScript (with a binary heap)

// The graph as adjacency lists: { A: [{to: 'B', w: 4}, {to: 'C', w: 1}], ... }
class MinHeap {
  constructor() { this.a = []; }
  isEmpty() { return this.a.length === 0; }
  push(item) { this.a.push(item); this._siftUp(this.a.length - 1); }
  pop() {
    if (this.a.length === 0) return null;
    const top = this.a[0];
    const last = this.a.pop();
    if (this.a.length) { this.a[0] = last; this._siftDown(0); }
    return top;
  }
  _siftUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.a[p].priority <= this.a[i].priority) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.a.length;
    while (true) {
      let l = i * 2 + 1, r = i * 2 + 2, m = i;
      if (l < n && this.a[l].priority < this.a[m].priority) m = l;
      if (r < n && this.a[r].priority < this.a[m].priority) m = r;
      if (m === i) break;
      [this.a[i], this.a[m]] = [this.a[m], this.a[i]];
      i = m;
    }
  }
}

function dijkstra(graph, source) {
  const dist = Object.create(null);
  const parent = Object.create(null);
  const pq = new MinHeap();

  for (const v of Object.keys(graph)) {
    dist[v] = Infinity;
    parent[v] = null;
  }
  dist[source] = 0;
  pq.push({ node: source, priority: 0 });

  while (!pq.isEmpty()) {
    const { node: u, priority: du } = pq.pop();
    if (du > dist[u]) continue; // stale entry

    for (const { to: v, w } of graph[u]) {
      if (w < 0) throw new Error('Dijkstra requires non-negative weights');
      const nd = dist[u] + w;
      if (nd < dist[v]) {
        dist[v] = nd;
        parent[v] = u;
        pq.push({ node: v, priority: nd });
      }
    }
  }

  return { dist, parent };
}

function reconstructPath(parent, source, target) {
  const path = [];
  let cur = target;
  if (parent[cur] === null && cur !== source) return []; // no path
  while (cur != null) {
    path.push(cur);
    if (cur === source) break;
    cur = parent[cur];
  }
  path.reverse();
  return path;
}

// Example
const graph = {
  A: [{ to: 'B', w: 4 }, { to: 'C', w: 1 }],
  B: [{ to: 'A', w: 4 }, { to: 'C', w: 2 }, { to: 'E', w: 4 }],
  C: [{ to: 'A', w: 1 }, { to: 'B', w: 2 }, { to: 'D', w: 4 }],
  D: [{ to: 'C', w: 4 }, { to: 'E', w: 1 }],
  E: [{ to: 'B', w: 4 }, { to: 'D', w: 1 }]
};

const { dist, parent } = dijkstra(graph, 'A');
console.log(dist); // { A:0, B:3, C:1, D:5, E:6 }
console.log(reconstructPath(parent, 'A', 'E')); // [ 'A', 'C', 'D', 'E' ]

How to reconstruct the path

We keep parent[v], the predecessor on the shortest path. After the algorithm runs, we walk from the target vertex backward via parent to the source and reverse the sequence.

Edge cases and pitfalls

Negative edges/cycles are not supported: use Bellman-Ford or Johnson's algorithm.
Disconnected graphs: dist stays ∞ for unreachable vertices.
Early exit: if you only need the path to a single target t, you can stop right after t is dequeued.
0-1 weights: use 0-1 BFS (a double-ended queue) for O(V+E).
Adjacency matrix: convenient O(V^2) without a heap for dense graphs.
Bidirectional search (bidirectional Dijkstra) speeds up the search between two vertices in large graphs.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.