Learn C++ STL

Lesson 3 of 9 · The STL in Competitive Programming: Which Container for Which Problem

Module 16 · The STL in Competitive Programming: Which Container for Which Problem

Dijkstra: Roads, Current Distances, and Stale Heap Entries

ProReading

David delivers books along one-way roads. Each road takes a known nonnegative number of minutes. The road with the smallest individual cost need not belong to the quickest whole journey. He needs the cheapest complete route from the library to every destination.

Checking what this lesson needs for you…

What is inside Dijkstra: Roads, Current Distances, and Stale Heap Entries

  1. Store roads beside their starting node
  2. Distances are current claims
  3. Pop the smallest distance, then check freshness
  4. Why settling is safe
  5. The full directed shortest-path program
  6. Costs follow successful relaxations
  7. Several sources use the same loop
  8. Adapt the transition only after proving it