Dijkstra's algorithm

Dijkstra finds the shortest path from a source to every node in a graph with non-negative edge weights. A priority queue always expands the closest unsettled node, so each node is settled once.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

Explain why expanding the closest unsettled node is correct with non-negative weights
Write Dijkstra with a priority queue and trace it on a small graph
Spot the negative edge that breaks the greedy argument

In practice

A few lines that show Dijkstra's algorithm doing its job.

Python

import heapq

def dijkstra(graph, source):          # graph[u] = [(v, weight), ...]
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float("inf")):
            continue                  # a stale entry, already improved
        for v, w in graph[u]:
            if d + w < dist.get(v, float("inf")):
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

The common mistake

Watch for

Running it on a graph with a negative edge. The greedy settling step assumes a path cannot get shorter later, which a negative weight breaks; use Bellman-Ford there.

What to know first

Your roadmap puts these before Dijkstra's algorithm, unless you already know them.

How it stays learned

Once a session shows you understand Dijkstra's algorithm, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

Day 3First recall, while it is fresh
Day 7Second, a week on
Day 18Last, when it has settled

Next in the moduleTopological sort →