Shortest PathO((V + E) log V)· Level 03

Dijkstra's Shortest Path

Cheapest route in a non-negative weighted graph.

Intuition

Dijkstra is greedy: it always extends the cheapest known path next. Picture a wave that travels faster on highways and slower on dirt roads — wherever the wave arrives first, that's the shortest distance.

Step-by-step

1
Initialise `dist[s] = 0` and `dist[v] = ∞` for every other vertex.
2
Insert `(0, s)` into a min-heap (priority queue).
3
Pop the vertex `u` with the smallest tentative distance.
4
For each neighbor `v` with edge weight `w`: if `dist[u] + w < dist[v]`, relax — update `dist[v]` and push it back into the heap.
5
Repeat until the heap is empty. Every popped vertex has its final shortest distance.

Pseudocode

pseudocode

DIJKSTRA(G, s):
  dist[v] = INF for all v
  dist[s] = 0
  PQ = min-heap of (0, s)
  while PQ not empty:
    (d, u) = PQ.pop()
    if d > dist[u]: continue
    for (v, w) in G.neighbors(u):
      if dist[u] + w < dist[v]:
        dist[v] = dist[u] + w
        PQ.push((dist[v], v))

Implementation (Python)

python

import heapq

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

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph.neighbors(u):
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))

    return dist

Real-world applications

GPS navigation (Google Maps, Waze)
Network routing protocols (OSPF)
Game AI pathfinding on weighted terrain