Skip to content

Shortest Paths (Dijkstra)

In one sentence

When edges have different non-negative lengths, always finalise the unvisited vertex that is currently closest to the start, and use a heap to find it fast. That is Dijkstra's algorithm.

1. What problem does it solve?

Example — 20C · Dijkstra? (5-Graph · L, rating 1900)

A weighted undirected graph has \(n\) vertices and \(m\) edges. Print a shortest path from vertex \(1\) to vertex \(n\), or -1 if there is none. The graph may have loops and multiple edges.

Limits: \(n, m \le 10^5\), \(w \le 10^6\).

Input      Output
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1      1 4 3 5

graph LR
  1 ---|2| 2
  2 ---|5| 5
  2 ---|4| 3
  1 ---|1| 4
  4 ---|3| 3
  3 ---|1| 5
  linkStyle 3,4,5 stroke:#4caf50,stroke-width:4px

The route \(1 \to 2 \to 5\) uses only \(2\) edges but costs \(2 + 5 = 7\). The green route \(1 \to 4 \to 3 \to 5\) uses \(3\) edges and costs \(1 + 3 + 1 = 5\). Fewer edges is not cheaper, so BFS (which counts edges) gives the wrong answer here.

2. The math

2.1 Words

  • \(\delta(v)\): the true shortest distance from the start \(s\) to \(v\).
  • dist[v]: our current best guess. It starts at \(0\) for \(s\) and \(\infty\) for everything else, and only ever goes down.
  • Relaxing edge \(u \to v\) with length \(w\): if dist[u] + w < dist[v], set dist[v] = dist[u] + w. "Going through \(u\) is better than what I knew." An undirected edge is relaxed in both directions.

2.2 Dijkstra's rule

Keep a set \(S\) of finished vertices, starting empty.

  1. Pick the unfinished vertex \(u\) with the smallest dist[u].
  2. Mark \(u\) finished, and relax every edge \(u \to v\).
  3. Repeat until every vertex is finished.

2.3 Why the smallest one is already correct

Claim. When \(u\) is picked in step 1, dist[u] \(= \delta(u)\).

Proof. Suppose some path \(P\) from \(s\) to \(u\) is shorter than dist[u]. \(P\) starts inside \(S\) (at \(s\)) and ends outside \(S\) (at \(u\)), so it has a first vertex \(y\) outside \(S\), reached by an edge \(x \to y\) with \(x \in S\).

  • \(x\) was finished earlier, so edge \(x \to y\) was relaxed then: dist[y] \(\le\) dist[x] \(+ w(x, y)\) \(=\) the length of \(P\) up to \(y\).
  • All lengths are non-negative, so the part of \(P\) after \(y\) adds \(\ge 0\): length of \(P\) up to \(y\) \(\le\) length of \(P\).
  • So dist[y] \(\le\) length of \(P\) \(<\) dist[u].

But \(y\) is unfinished and has a smaller dist than \(u\), so step 1 should have picked \(y\), not \(u\). Contradiction. \(\blacksquare\)

Negative edges break this

The middle bullet needs every length \(\ge 0\). With a negative edge, a path can get shorter after leaving \(S\), and a finished vertex could still improve. Dijkstra is then wrong or very slow.

2.4 A heap finds "the smallest" fast

Push (dist, vertex) pairs into a min-heap (heapq). Python compares tuples by the first item, so the heap top is always the closest one.

When dist[v] improves, we simply push a new pair and leave the old, larger pair in the heap. When a stale pair comes out later, skip it:

cur_dist, cur_node = heapq.heappop(q)
if cur_dist > dist[cur_node]:
    continue            # an old, outdated entry

To print the path, also remember parent[v] = u whenever dist[v] improves.

Trace on the example:

pop skip? relax (new dist, parent) dist[1..5] after heap after
— 0 ∞ ∞ ∞ ∞ (0,1)
(0,1) no 2: 2 (p=1), 4: 1 (p=1) 0 2 ∞ 1 ∞ (1,4) (2,2)
(1,4) no 3: \(1+3 = 4\) (p=4) 0 2 4 1 ∞ (2,2) (4,3)
(2,2) no 5: \(2+5 = 7\) (p=2); 3: \(2+4 = 6\), not better 0 2 4 1 7 (4,3) (7,5)
(4,3) no 5: \(4+1 = 5 < 7\) (p=3); 2: \(4+4\), not better 0 2 4 1 5 (5,5) (7,5)
(5,5) no nothing better 0 2 4 1 5 (7,5)
(7,5) yes, \(7 > 5\) empty

Walking parent back from \(5\): \(5 \to 3 \to 4 \to 1\). Reversed: 1 4 3 5.

2.5 Cost

Each edge can push at most one pair per direction, so the heap holds \(O(m)\) items, and each push or pop costs \(O(\log m)\). Total: \(O((n + m) \log m)\).

3. Template — from our lesson (May 3)

This dijkstra is from our lesson code for 545E · Paths and Trees. Besides the distances, it remembers which edge reached each vertex, and among equally short ways it prefers the lighter last edge. The core of every Dijkstra is in it: dist, the heap, the stale-entry skip, and relaxation.

inf = 10 ** 30


def dijkstra(graph, start):
    dist = [inf for _ in graph]

    parent_edge = [-1] * len(graph)
    parent_weight = [inf] * len(graph)

    dist[start] = 0
    q = [(0, start)]

    while q:
        cur_dist, cur_node = heapq.heappop(q)
        if cur_dist > dist[cur_node]:
            continue

        for nxt_node, weight, edge_idx in graph[cur_node]:
            nxt_dist = dist[cur_node] + weight

            if nxt_dist < dist[nxt_node]:
                dist[nxt_node] = nxt_dist
                parent_edge[nxt_node] = edge_idx
                parent_weight[nxt_node] = weight
                heapq.heappush(q, (nxt_dist, nxt_node))

            elif nxt_dist == dist[nxt_node] and weight < parent_weight[nxt_node]:
                parent_weight[nxt_node] = weight
                parent_edge[nxt_node] = edge_idx

    return parent_edge, parent_weight

graph[u] holds tuples (neighbour, weight, edge index), and vertices are \(0\)-indexed.

4. Worked solution — Dijkstra?

This is the lesson template with parent (the previous vertex) instead of the parent edge, and without the tie-break, which this problem does not need. Roads are undirected, so each edge is added in both directions.

import sys
import heapq

input = sys.stdin.readline

inf = 10 ** 30


def dijkstra(graph, start):
    dist = [inf for _ in graph]
    parent = [-1] * len(graph)

    dist[start] = 0
    q = [(0, start)]

    while q:
        cur_dist, cur_node = heapq.heappop(q)
        if cur_dist > dist[cur_node]:
            continue

        for nxt_node, weight in graph[cur_node]:
            nxt_dist = dist[cur_node] + weight

            if nxt_dist < dist[nxt_node]:
                dist[nxt_node] = nxt_dist
                parent[nxt_node] = cur_node
                heapq.heappush(q, (nxt_dist, nxt_node))

    return dist, parent


def solve():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        a, b, w = map(int, input().split())
        graph[a - 1].append((b - 1, w))
        graph[b - 1].append((a - 1, w))

    dist, parent = dijkstra(graph, 0)

    if dist[n - 1] == inf:
        print(-1)
        return

    path = []
    cur = n - 1
    while cur != -1:
        path.append(cur)
        cur = parent[cur]
    path.reverse()

    for v in path:
        print(v + 1, end=" ")
    print()


solve()

The walk back stops at the start because parent[0] is never set and stays -1.

5. Tricks from our problem sets

trick how problem
print the path store parent[v] = u when relaxing, walk back from the end 20C · Dijkstra?, 5-Graph · L (this page)
shortest path tree: cheapest set of edges keeping all distances on ties, keep the lighter last edge (the lesson template) 545E · Paths and Trees, 5-Graph · N
virtual source: "start anywhere, paying \(a_i\) to start at \(i\)" add a vertex \(0\) with an edge \(0 \to i\) of length \(a_i\), then run from \(0\) 938D · Buy a Ticket, 5-Graph · O
two kinds of edges: which trains are unnecessary run Dijkstra on roads + trains; a train is needed only if it is the unique shortest way (lesson code May 3, used_train) 449B · Jzzhu and Cities, 5-Graph · P
keep only \(k\) edges the edges of the shortest path tree, in the order vertices are finalised 1076D · Edge Deletion, 5-Graph · M
all edges the same length plain BFS is enough and faster

6. Common mistakes

inf too small

Distances can reach \(10^6 \cdot 10^5 = 10^{11}\) here, and more in other problems. inf = 10**9 is not infinity. The template uses 10 ** 30.

No stale-entry skip

Without if cur_dist > dist[cur_node]: continue, old heap entries relax their edges again. The answer stays correct, but on bad inputs it becomes very slow (TLE). 20C has tests built to catch this.

(node, dist) in the heap

heapq compares the first item. Pushing (node, dist) pops the smallest vertex number, not the closest vertex. Always push (dist, node).

Undirected roads added once

A two-way road needs both graph[a].append(...) and graph[b].append(...).

Forgetting the -1 case

If \(n\) is unreachable, dist[n - 1] stays inf and walking parent from it prints just n. Check first.

Negative edges

Dijkstra's proof needs \(w \ge 0\) (§2.3). Negative edges need Bellman–Ford, which is not covered here.

7. Practice

Problem Set Rating Idea
20C · Dijkstra? 5-Graph · L 1900 Dijkstra + print the path (this page)
1076D · Edge Deletion 5-Graph · M 1800 keep the first \(k\) edges of the shortest path tree
545E · Paths and Trees 5-Graph · N 2000 lesson template
938D · Buy a Ticket 5-Graph · O 2000 virtual source
449B · Jzzhu and Cities 5-Graph · P 2000 roads vs. trains
Credits & licenses