The cheapest way from one place to every other place when roads have different lengths.
The idea (a GPS)
BFS finds the path with the fewest roads, but real roads have different lengths. Dijkstra finds the path with the smallest total length. It keeps a notebook of the best known distance to every place, starting with ∞ (unknown) everywhere except the start (0).
Pick the unfinished place with the smallest known distance. Nothing can beat it, because every other route to it would have to pass through a place that is already farther away. So its distance is final.
From it, try each road: is distance so far + road length smaller than what we have written for the neighbor? If yes, relax the edge: update the notebook.
Repeat until nothing is left.
The “pick the smallest” step is a priority queue (a min-heap, see the heap page). It requires every road length to be positive.
Watch it work
Roads work in both directions. Nodes are numbered 0, 1, 2, ... with no gaps (at most 10 nodes, 15 roads). Lengths are whole numbers from 1 to 99.
Try it
Look at the default graph. The direct road 0–1 has length 4, but the answer for node 1 is 3. Which route wins?
Change 0-1:4 to 0-1:2 and run again. What changes?
Add a node with no roads to the rest, such as 0-1:1, 2-3:1 (start 0). What distance do 2 and 3 keep?
Watch for the “stale entry” step: the queue can hold an old, longer distance for a node that already got a better one.
Common mistakes
Negative road lengths. Dijkstra assumes a finished node can never be improved. A negative edge breaks that (use Bellman-Ford instead).
Forgetting the stale check. Without if cur.dist > dist[cur.node] { continue } you redo work for outdated queue entries.
Using a plain queue. It must always hand back the smallest distance, not the oldest entry.
Using 0 as “infinity”. Use a very large number (or a map with a presence check) for unknown distances.
Complexity, in plain English: each road may add one entry to the priority queue, and each queue operation costs about log(entries). So the time is about O((V + E) log V). It is fast even on big maps, but it still needs memory for the distances and the queue.