Algorithm Guidecomplexity: O(E log V)

Dijkstra

Finds the shortest distances from a source node in a weighted graph with no negative edges. Its greedy strategy uses a priority queue to fix the closest node each round and relax its neighbors, making it the standard for navigation and network routing.

01Dijkstra

Explore How It Works

Starting Dijkstra. The distance to source node A is 0; every other node is still unknown, so it starts at ∞.

Extract A, the closest node so far, and fix it. Measure the routes to neighbors B·C.

Going from A to B costs 6. B had no route at all, so write down 6.

Going from A to C costs 1. C is closer than B, so it is fixed next.

Extract the closest node, C, and fix it. Measure the routes to its neighbors B·D.

Reaching B through C costs 3 — shorter than the 6 of going straight there. Overwrite it with the shorter route.

Going from C to D costs 6. It is the first route measured there, so write it down as is.

The closest node now is B. Fix it and measure the route to D again.

Reaching D through B costs 4 — shorter than the 6 written earlier, so overwrite it.

Fix D and measure the distance to the last neighbor, E.

Adding the edge from D to E gives 6. The last node's distance is settled.

Extract E and fix it. No nodes are left to examine, so every shortest distance is final.

Done · shortest path from A to E is A → C → B → D → E (distance 6). The highlighted edges form the shortest-path tree.

Live Python

1import heapq

2def dijkstra(graph, start):

# dist[A] = 0

3 dist = {start: 0}

4 pq = [(0, start)]

5 visited = set()

6 while pq:

7 d, u = heapq.heappop(pq)

8 if u in visited:

9 continue

10 visited.add(u)

11 for v, w in graph[u]:

12 nd = d + w

13 if nd < dist.get(v, INF):

14 dist[v] = nd

15 heapq.heappush(pq, (nd, v))

16 return dist

1 / 13

02 Understand It Simply

For Everyone

🔑How It Works

Finalizes the shortest distance one vertex at a time, always taking the nearest unfinalized vertex. Negative edge weights break that finality.

💡In Plain Words

Uses a priority queue to lock in the closest node one at a time and expand the shortest distances outward.

Fast and exact when there are no negative edges.

📍Where It's Used

–Navigation
–network routing
–shortest paths

03 Python Implementation

A clean, readable reference implementation of the core logic of Dijkstra.

core_implementation.py

import heapq

def dijkstra(graph, start):
    dist = {start: 0}
    pq = [(0, start)]
    visited = set()
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist