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.

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

python

▶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

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.

06

Complexity

Time

O((V + E) log V)

Space

O(V + E)

Binary heap; each edge can push at most once.