Graph AlgosGraph Algorithms

Dijkstra's Algorithm

Single-source shortest paths on graphs with non-negative edge weights, greedily settling the closest unsettled node using a min-priority queue.

Learn Dijkstra's Algorithm →
42518103263A0B∞C∞D∞E∞F∞G∞
Priority queue (min first)
nodedist
A0
1/22All distances start at ∞ except dist[A] = 0. The priority queue always hands us the closest unsettled node, which is what makes greedy settling correct with non-negative weights.
Settled now (popped)In priority queueSettledEdge being relaxedBest-known parent edgeShortest path
PseudocodeLearn Dijkstra's Algorithm →
1dist = {v: ∞}; dist[source] = 0; pq = [(0, source)]
2while pq not empty:
3  (d, u) = pq.pop_min()
4  if d > dist[u]: continue   # stale entry
5  for (v, w) in neighbors(u):
6    if dist[u] + w < dist[v]:
7      dist[v] = dist[u] + w; parent[v] = u
8      pq.push((dist[v], v))
9path = follow parent from target back to source
Complexity
best O(V log V)
avg O((V + E) log V)
worst O((V + E) log V)
space O(V + E)
Speed