Workspace

Problem workspace

3 day streakD

Dijkstra’s Algorithm

MediumGraphsShortest paths

The challenge

Compute shortest distances from one source in a weighted graph whose edge weights are all nonnegative.

Negative weights invalidate the settling argument. Use Bellman–Ford when negative edges may occur.

Example

From A: A:0, B:3, C:4, D:7, E:8, F:1. A → F → B beats the direct A → B edge.

Use the walkthrough below to inspect the input and each state change.

See Dijkstra, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 7 edgesA = 0, B = 1, …
Weighted graphDirected graph with 6 vertices. Set distance[A] = 0. All edge weights must be nonnegative. Unreached vertices begin at infinity. The edge list and state table below provide the graph in text.4121831ABCDEF
CurrentVisited / acceptedUnvisited
Best distance from source
ABCDEF
0∞∞∞∞∞
Step 01 / 17

Set distance[A] = 0.

All edge weights must be nonnegative. Unreached vertices begin at infinity.

push(0, A)

Min-priority queue · smallest first

A:0
View input edges

A → B (4) · A → F (1) · F → B (2) · B → C (1) · F → E (8) · C → D (3) · D → E (1)

Source: A. Adjacency entries follow this edge order.

Put it into code

Always process the smallest tentative distance; ignore old queue entries.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from heapq import heappop, heappush
from math import inf

def dijkstra(adj, source):
    # adj[u] contains (v, weight); ALL weights >= 0.
    distance = [inf] * len(adj)
    distance[source] = 0
    heap = [(0, source)]

    while heap:
        d, u = heappop(heap)
        if d != distance[u]:
            continue  # Discard an outdated queue entry.
        for v, weight in adj[u]:
            candidate = d + weight
            if candidate < distance[v]:
                distance[v] = candidate
                heappush(heap, (candidate, v))

    return distance

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap