{ }SolveLogs
⌕
Home / Graphs / GFG
GeeksforGeeks Medium

Dijkstra's Algorithm

Dijkstra's Algorithm is a GFG problem (Medium). You are given a connected, undirected, weighted graph with V vertices numbered 0 … V-1, as a list edges where edges[i] = [u, v, w] is an edge between u and v of weight w, and a source vertex src.

Return an array dist of length V where dist[i] is the shortest distance from src to vertex i.

  • Every weight is non-negative. That condition is what makes Dijkstra's algorithm correct.
  • V and E go up to 10⁶, so a min-heap that keeps the work near O(E log V) is the expected answer.
Constraints
  • 1 <= V <= 10⁶
  • 1 <= E <= 10⁶
  • 0 <= weight <= 10⁴ — non-negative only
  • Use Bellman-Ford if any edge can be negative
graphshortest-pathheapgreedy
Open on GeeksforGeeks ↗
02

Intuition

Dijkstra's algorithm grows a set of settled vertices, starting from the source. A settled vertex is one whose shortest distance is final and will never change.

  • Pick: always settle the closest unsettled vertex next.
  • Why that is safe: any other route to it must leave the settled set through a vertex that is already at least as far away. With non-negative weights, the rest of that route can only add distance, so nothing found later can beat it.
  • Relax: after settling u, check each neighbour v. If dist[u] + w is smaller than the best known dist[v], lower dist[v]. That update is called relaxing the edge.

A min-heap (priority queue) keyed by distance hands out the closest unsettled vertex in O(log V). When a distance is lowered, the old heap entry is left behind; it is stale (out of date) and is simply skipped when popped.

The demo below walks through a Dijkstra algorithm example on six vertices, including the stale entries it skips.

How to spot this pattern

Reach for Dijkstra shortest path whenever the task is a single source shortest path on a weighted graph where no edge is negative: road maps, network delay (LeetCode 743), cheapest flights without a stop limit, path with minimum effort (LeetCode 1631). If every edge has the same weight, plain BFS does the same job in O(V + E). If an edge can be negative, use Bellman-Ford.

03

Approach

Try it first

Before reading on: on the first example, which vertex would you settle second, and why is its distance already final? Then decide what to do when the heap hands you a vertex whose distance has since been improved.

Two ways to solve it

Min-heap (priority queue)Best
Time O((V + E) log V)Space O(V + E)

The heap hands out the closest unsettled vertex, and stale entries are skipped when popped.

  • Finding the next vertex: O(log V) per pop.
  • Fits: sparse graphs, like this one with E up to 10⁶.
  • Extra state: the heap, up to E entries.

The standard answer for this problem.

Solution & demo ↓
Array scan
Time O(V² + E)Space O(V + E)

Each round scans every vertex for the smallest unsettled distance, settles it, and relaxes its edges.

  • Finding the next vertex: O(V) per round.
  • Fits: dense graphs, where E is close to V².
  • Extra state: a settled flag per vertex.

Too slow at V = 10⁶.

Code ↓

With up to 10⁶ vertices and edges, the heap avoids the V² scan, so it is the one to use here. The steps, code and live demo below follow the heap version; the array-scan code comes after the demo.

1

Build the adjacency list

For each [u, v, w], add (v, w) to adj[u] and (u, w) to adj[v], because the graph is undirected. Each vertex then reaches its neighbours directly instead of scanning the whole edge list.

2

Initialise distances and the heap

dist is infinity everywhere except dist[src] = 0. The heap starts with (0, src). The source is the only distance known for sure at the start.

3

Pop the closest vertex

Pop (d, u) with the smallest d:

  • if d > dist[u], the entry is stale (u was already settled with a smaller distance), so skip it;
  • otherwise u is settled now, and dist[u] is final.
4

Relax every edge out of u

For each (v, w) in adj[u]: if d + w < dist[v], set dist[v] = d + w and push (dist[v], v). A shorter path to u may also give a shorter path to each neighbour. A vertex is final when it is popped, not when it is pushed.

5

Stop when the heap is empty

Every reachable vertex has been settled once with its final distance. Return dist.

04

Dijkstra's Algorithm solution in Python | C++ | Java

▶1class Solution:
▶2 def dijkstra(self, V: int, edges: List[List[int]], src: int) -> List[int]:
▶3 adj = [[] for _ in range(V)]
▶4 for u, v, w in edges:
▶5 adj[u].append((v, w))
▶6 adj[v].append((u, w))
▶7 dist = [float("inf")] * V
▶8 dist[src] = 0
▶9 pq = [(0, src)]
▶10 while pq:
▶11 d, u = heapq.heappop(pq)
▶12 if d > dist[u]:
▶13 continue
▶14 for v, w in adj[u]:
▶15 if d + w < dist[v]:
▶16 dist[v] = d + w
▶17 heapq.heappush(pq, (dist[v], v))
▶18 return dist
41215326012345dist001∞2∞3∞4∞5∞poppedheap00source 0: distance 0
src0distance 0
heap(0, 0)closest first
Start. Only the source has a known distance. The heap always hands out the unsettled vertex with the smallest tentative distance; with non-negative weights, that distance can no longer improve.
41215326012345dist0014was ∞21was ∞3∞4∞5∞popped00heap2114settle 0 at distance 0
u0closest unsettled
dist[0]0final
updated21: ∞ → 4, 2: ∞ → 1
Settle 0 at 0. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. Relaxing its edges improves 1 (∞ → 4), 2 (∞ → 1); each new distance is pushed onto the heap.
41215326012345dist0013was 42136was ∞4∞5∞popped21heap131436settle 2 at distance 1
u2closest unsettled
dist[2]1final
updated21: 4 → 3, 3: ∞ → 6
Settle 2 at 1. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. Relaxing its edges improves 1 (4 → 3), 3 (∞ → 6); each new distance is pushed onto the heap.
41215326012345dist00132134was 64∞5∞popped13heap143436settle 1 at distance 3
u1closest unsettled
dist[1]3final
updated13: 6 → 4
Settle 1 at 3. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. Relaxing its edges improves 3 (6 → 4); each new distance is pushed onto the heap.
41215326012345dist001321344∞5∞popped14heap3436stale entry for 1 → skip
popped(4, 1)old entry
dist[1]3settled earlier
Stale entry. This was pushed when the best route to 1 cost 4. A cheaper one (3) was found later and 1 is already settled, so expanding it again would only waste time.
41215326012345dist0013213447was ∞510was ∞popped34heap3647510settle 3 at distance 4
u3closest unsettled
dist[3]4final
updated24: ∞ → 7, 5: ∞ → 10
Settle 3 at 4. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. Relaxing its edges improves 4 (∞ → 7), 5 (∞ → 10); each new distance is pushed onto the heap.
41215326012345dist0013213447510popped36heap47510stale entry for 3 → skip
popped(6, 3)old entry
dist[3]4settled earlier
Stale entry. This was pushed when the best route to 3 cost 6. A cheaper one (4) was found later and 3 is already settled, so expanding it again would only waste time.
41215326012345dist001321344759was 10popped47heap59510settle 4 at distance 7
u4closest unsettled
dist[4]7final
updated15: 10 → 9
Settle 4 at 7. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. Relaxing its edges improves 5 (10 → 9); each new distance is pushed onto the heap.
41215326012345dist001321344759popped59heap510settle 5 at distance 9
u5closest unsettled
dist[5]9final
updated0none
Settle 5 at 9. It is the closest unsettled vertex, and any other route would leave the settled set farther out and could only add distance. None of its edges beats a known distance, so nothing is pushed.
41215326012345dist001321344759popped510heapemptystale entry for 5 → skip
popped(10, 5)old entry
dist[5]9settled earlier
Stale entry. This was pushed when the best route to 5 cost 10. A cheaper one (9) was found later and 5 is already settled, so expanding it again would only waste time.
41215326012345dist001321344759poppedheapemptydist final → return dist
dist[0, 3, 1, 4, 7, 9]from vertex 0
Done. Every vertex was settled once, at its final distance. The green edges are the ones each vertex was last reached through: together they form the shortest-path tree from 0.
05

Dijkstra with an array scan

Run V rounds. Each round picks the unsettled vertex with the smallest dist by a linear scan, stops if that distance is infinite, marks it settled, and relaxes its edges.

▶1class Solution:
▶2 def dijkstra(self, V: int, edges: List[List[int]], src: int) -> List[int]:
▶3 adj = [[] for _ in range(V)]
▶4 for u, v, w in edges:
▶5 adj[u].append((v, w))
▶6 adj[v].append((u, w))
▶7 dist = [float("inf")] * V
▶8 dist[src] = 0
▶9 done = [False] * V
▶10 for _ in range(V):
▶11 u = -1
▶12 for i in range(V):
▶13 if not done[i] and (u == -1 or dist[i] < dist[u]):
▶14 u = i
▶15 if dist[u] == float("inf"):
▶16 break
▶17 done[u] = True
▶18 for v, w in adj[u]:
▶19 if dist[u] + w < dist[v]:
▶20 dist[v] = dist[u] + w
▶21 return dist
06

Common pitfalls

Processing 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

The answer stays correct, but a vertex whose distance was lowered k times is expanded k times. On dense graphs that turns O(E log V) into much more work, and it is the usual reason a Dijkstra solution times out.

Using Dijkstra with negative edge weights

✗ Wrong
# directed: 0→1 (2), 0→2 (5), 2→1 (-4)
# 1 is settled at distance 2 and treated as final
✓ Right
# any negative edge: use Bellman-Ford
# dist[1] = 5 + (-4) = 1

Dijkstra is correct only because a popped vertex is final. With a visited set, vertex 1 is locked at 2 before the cheaper route through 2 is found. The lazy version on this page happens to reopen it, but then vertices can be expanded again and again, and on some graphs the running time becomes exponential.

Marking a vertex visited when it is pushed

✗ Wrong
if v not in seen:
    seen.add(v)
    heapq.heappush(pq, (d + w, v))
✓ Right
if d + w < dist[v]:
    dist[v] = d + w
    heapq.heappush(pq, (dist[v], v))

That is BFS logic. In the second example vertex 3 is first reached by the direct edge of cost 10 and would be locked at 10, although the path through 1 and 2 costs 3. A vertex is final when it is popped, not when it is first seen.

07

Complexity

Time
O((V + E) log V)
Space
O(V + E)
Each edge can push one heap entry, so the heap holds O(E) items and each push or pop costs O(log E) = O(log V). The adjacency list and the heap are the space.
08

Dijkstra vs other shortest-path algorithms

The weights and the number of sources decide which algorithm is correct and fastest.

AlgorithmWeightsSourcesTime
BFSall equaloneO(V + E)
0-1 BFS (deque)only 0 or 1oneO(V + E)
Dijkstra (min-heap)non-negativeoneO((V + E) log V)
Bellman-Fordany, detects negative cyclesoneO(V · E)
Floyd Warshallany, detects negative cyclesall pairsO(V³)
09

Dijkstra's Algorithm FAQ

How does Dijkstra's algorithm work?
  • Start: dist[src] = 0, every other distance infinity, heap = [(0, src)].
  • Repeat: pop the vertex u with the smallest distance; skip it if the entry is stale (d > dist[u]).
  • Relax: for each edge (u, v, w), if dist[u] + w < dist[v], update dist[v] and push it.
  • End: when the heap is empty, dist holds shortest distances.
  • Requirement: no negative edge weights.
  • Complexity: O((V + E) log V) with a binary heap.
What is the time complexity of Dijkstra's algorithm?

O((V + E) log V) with a binary heap, since each edge may add one heap entry and each heap operation is O(log V).

← Prev · GFG
DFS of Graph
Next · GFG →
Find Missing and Repeating Number