Dijkstra's Algorithm

#How does it work?

Dijkstra's algorithm (Edsger Dijkstra, 1956) finds the shortest (cheapest) paths from a start node to every other node in a graph whose edge weights are not negative.

BFS minimises the number of edges, but when edges have different lengths, times or costs, the path with the fewest edges may not be the cheapest. In the example graph the BFS path 1 → 2 → 4 → 7 costs 12, while Dijkstra's 1 → 3 → 6 → 7 costs 6.

The algorithm is greedy: at each step it picks the unsettled node with the smallest distance and settles it. Because weights are never negative, a shorter route to that node can't turn up later.

The settled node's neighbours are then "relaxed": if dist[u] + w is smaller than dist[v], dist[v] is updated and prev[v] = u is recorded. A priority queue (min-heap) finds the node with the smallest distance quickly.

#Try it yourself

#Step by step

1. 01Set dist[start] = 0 and every other distance to ∞; put the start in the priority queue.
2. 02Take the node u with the smallest distance from the queue and settle it.
3. 03For each unsettled neighbour v of u: if dist[u] + w(u, v) < dist[v], update dist[v], set prev[v] = u and add v to the queue.
4. 04Repeat until the queue is empty (or the target is settled); read the path by following prev[] back from the target.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

import heapq

# Undirected weighted graph: graph[u] = [(v, weight), ...]
EDGES = [(1, 2, 4), (1, 3, 1), (2, 4, 5), (2, 5, 2), (3, 5, 2), (3, 6, 4), (4, 7, 3), (5, 7, 6), (6, 7, 1)]
graph = {v: [] for v in range(1, 8)}
for a, b, w in EDGES:
    graph[a].append((b, w))
    graph[b].append((a, w))


def dijkstra(start: int):
    dist = {v: float("inf") for v in graph}
    prev = {}
    dist[start] = 0
    heap = [(0, start)]  # (distance, node), smallest first
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # an outdated entry: u was already settled with a smaller distance
        for v, w in graph[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    return dist, prev


dist, prev = dijkstra(1)
print(" ".join(str(dist[v]) for v in range(1, 8)))  # distance from 1 to nodes 1..7

path = [7]
while path[-1] != 1:
    path.append(prev[path[-1]])
print(" ".join(map(str, reversed(path))))  # cheapest path, not the fewest edges (1 2 4 7)
print(dist[7])

#Complexity

Each edge is relaxed at most once, and each relaxation may push onto the heap at O(log V). On dense graphs (E ≈ V²) the plain array version can be faster. With negative edge weights Dijkstra gives wrong answers; use Bellman-Ford instead.

#When to use it?

Route finding in maps and navigation apps, network routing protocols (OSPF), pathfinding in games (A* is a heuristic extension of Dijkstra), flight and transit planning: every "cheapest/fastest route" problem is solved with Dijkstra.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Bellman-Ford Algorithm
• Floyd-Warshall Algorithm
• Prim's Algorithm