Suggest an edit

Improve this article

Refine the answer for “How does Dijkstra's algorithm work on graphs?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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).

1. Initialization: dist[source] = 0, ∞ for the rest; parent[v] = null.
2. Put source into the priority queue keyed by dist.
3. While the queue is not empty: dequeue the vertex u with the minimal dist[u]. If the extracted estimate is stale, skip it.
4. 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].
5. 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=∞.

1. Dequeue A (0). Relaxations: B ← 4, C ← 1. dist: A=0, B=4, C=1, D=∞, E=∞.
2. 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=∞.
3. Dequeue B (3). Relaxations: E ← 3+4=7. dist: A=0, B=3, C=1, D=5, E=7.
4. Dequeue D (5). Relaxations: E ← min(7, 5+1=6) → 6. dist: A=0, B=3, C=1, D=5, E=6.
5. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts1167 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.