GeeksforGeeks Medium

Dijkstra's Algorithm

Shortest distance from a source to every vertex, with non-negative edge weights.

graphshortest-pathheapgreedy

02

Intuition

Repeatedly finalise the nearest vertex that is not yet settled. This works precisely because weights are non-negative: any other route to that vertex would have to pass through something even further away, which can only add cost. So the closest unsettled vertex can never improve later — settle it and relax its edges.

How to spot this pattern

Shortest paths with non-negative weights. A plain BFS queue fails once edges carry different costs, so the queue becomes a priority queue ordered by distance — that's the entire modification. The greedy is safe only because weights are non-negative: a settled vertex can never be improved by a longer detour. Negative edges break that and require Bellman-Ford.

03

Approach

1

Greedy settle order

Keep tentative dist[], all ∞ except the source. Pick the smallest unsettled distance, mark it settled, and relax its outgoing edges: dist[v] = min(dist[v], dist[u] + w).

2

Use a heap

Scanning for the minimum is O(V) per step, giving O(V²). A binary heap makes it O(log V), for O((V + E) log V) overall — push improved distances and skip stale heap entries.

3

Why negative weights break it

A negative edge could make a far-away route cheaper after a vertex was settled, violating the settle-once guarantee. Use Bellman–Ford in that case.

04

Solution & live demo

▶1import heapq
▶2 
▶3def dijkstra(n, edges, src):
▶4    adj = [[] for _ in range(n)]
▶5    for u, v, w in edges:
▶6        adj[u].append((v, w))
▶7    dist = [float("inf")] * n
▶8    dist[src] = 0
▶9    pq = [(0, src)]
▶10    while pq:
▶11        d, u = heapq.heappop(pq)
▶12        if d > dist[u]:           # stale entry
▶13            continue
▶14        for v, w in adj[u]:       # relax edges out of u
▶15            if d + w < dist[v]:
▶16                dist[v] = d + w
▶17                heapq.heappush(pq, (dist[v], v))
▶18    return dist

05

Common pitfalls

Not skipping stale heap entries

✗ Wrong

d, u = heapq.heappop(pq)
for v, w in adj[u]: ...

✓ Right

d, u = heapq.heappop(pq)
if d > dist[u]:
    continue

Vertices are pushed again whenever a shorter route is found, so the heap accumulates outdated pairs. Processing one re-expands a vertex using a distance already beaten — correct answers, but wasted work that can dominate the runtime on dense graphs.

Marking vertices visited instead of comparing distances

✗ Wrong

if seen[u]: continue
seen[u] = True

✓ Right

if d > dist[u]: continue

A visited flag works here, but comparing against dist[u] is strictly more informative and is what generalises to variants that revisit vertices. It also needs no extra array.

Pushing without relaxing first

✗ Wrong

for v, w in adj[u]:
    heapq.heappush(pq, (d + w, v))

✓ Right

if d + w < dist[v]:
    dist[v] = d + w
    heapq.heappush(pq, (dist[v], v))

Pushing every edge unconditionally makes the heap grow to O(E) with entries that will never improve anything. Only a genuine improvement deserves a push.

06

Edge cases

Unreachable vertex

Distance stays ∞.

Stale heap entries

Pop and skip any entry whose distance exceeds the recorded dist[u].

Zero-weight edges

Fine — only strictly negative weights break the argument.

07

Complexity

Time

O((V + E) log V)

Space

O(V + E)

Binary heap; each edge can push at most once.