Home/Graphs/Dijkstra
Search algorithmsCTRL K

Dijkstra

· shortest paths · non-negative weights
/graphs/dijkstra
SETTLED
0/ 10
nodes with final distance
HEAP
1
entries waiting
RELAXED
0
distances improved
EDGES
0
looked at so far
DIST
0
of the current node
settlingedge examinedtentative · parent edgesettled
10 nodes · 11 edges · seed 7 · 34 steps
step 0 / 33
Nodes10
dijkstra.ts
1
function dijkstra(graph: Graph, source: Node) {
2
  const dist = new Map([[source, 0]]);
3
  const open = new MinHeap([[0, source]]);
4
  while (open.size > 0) {
5
    const [distance, node] = open.pop(); // smallest dist
6
    if (distance > dist.get(node)!) continue;
7
    for (const [neighbor, weight] of graph.edges(node)) {
8
      const newDistance = distance + weight;
9
      if (newDistance >= (dist.get(neighbor) ?? Infinity)) continue;
10
      dist.set(neighbor, newDistance);
11
      open.push([newDistance, neighbor]);
12
    }
13
  }
14
  return dist;
15
}
CURRENT STEP
line 2

Source A gets distance 0; every other node is at ∞.

// how it works

Understanding Dijkstra

Dijkstra · settle the closest node, relax its edges, repeat
01

The idea

Dijkstra grows a set of settled nodes whose shortest distance is final. Each round it takes the unsettled node with the smallest tentative distance, settles it, and relaxes its edges: if going through it makes a neighbour closer, the neighbour's tentative distance and parent are updated.

It works because with non-negative weights no later path can beat the smallest tentative distance in the heap. The tree of parent edges is the shortest-path tree from the source to every node it reached.

02

The four stages

1
popsmallest tentative distance
2
settleits distance is final
3
examineeach edge out of it
4
relaxcheaper: new distance and parent
03

Complexity

best
O((V + E) log V)with a binary heap
average
O((V + E) log V)every edge relaxed at most once per settle
worst
O(E + V log V)with a Fibonacci heap
space
O(V + E)heap, distances and parents
04

Versus its siblings

EDGES EXAMINED · 1 000 NODES, 3 000 EDGES
bfs
6,000
dfs
6,000
dijkstra
6,000
bellman-ford
3M
floyd-warshall
1B
weighted graph: only Dijkstra, Bellman–Ford and Floyd–Warshall give correct distances
05

Pseudocode

DIJKSTRA(graph, source)
  dist[source] ← 0; heap ← {(0, source)}
  while heap not empty
    (distance, node) ← pop the smallest; skip if stale
    for each edge node–neighbour with its weight
      if distance + weight < dist[neighbour]: dist[neighbour] ← distance + weight; parent[neighbour] ← node; push (distance + weight, neighbour)
06

When to use

Road networks, network routing (OSPF, IS-IS), any graph with non-negative costs.
One source, all destinations: run it to exhaustion and read the whole tree.
07

Pitfalls

A negative edge breaks the settle-once guarantee. Bellman–Ford handles it, slower.
Stale heap entries: after a relaxation the old entry is still in the heap; skip it when popped instead of decreasing keys.
For one destination, stop when it is settled; running to exhaustion wastes the rest.
08

History

Edsger Dijkstra found the algorithm in 1956 while thinking about the shortest way between Rotterdam and Groningen, and published it in 1959. The heap-based version everyone uses came later; with Fibonacci heaps Fredman and Tarjan reached O(E + V log V) in 1984, still the best bound for sparse graphs.

Back to Graphs