Skip to content
CCC Python Course

Dijkstra's shortest paths

Stage
6
Module
M6.1
Lessons
1

In this module

  • Explain why settling the closest node first needs non-negative edge weights.
  • Implement Dijkstra's algorithm with Python's heapq module.
  • Skip out-of-date heap entries instead of updating them.
  • Store the graph and read input so the search runs fast on PyPy 3.8.

Before this module

M4.12Graphs I: modelling and adjacency listsM5.11Heaps and lazy deletion; ordered-set substitutes

Lessons

  1. 1Dijkstra's shortest paths

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2025 S4
    Floor is Lava (opens on WMOJ in a new tab) WMOJ

    Find the cheapest way through a set of rooms and tunnels of different temperatures.

  2. 2023 S4
    Minimum Cost Roads (opens on WMOJ in a new tab) WMOJ

    Keep the cheapest set of roads that leaves every shortest distance unchanged.

  3. 2015 S4
    Convex Hull (opens on DMOJ in a new tab) DMOJ

    Find the fastest crossing between islands while keeping hull damage under a limit.

    Why DMOJ: An older weighted shortest-path problem that still makes good practice for this module.