Graphs · 20 min

Dijkstra's algorithm: settle the closest node first

Shortest paths by greedily settling nodes in order of distance, and the one assumption that makes it work.

Builds onBreadth-first and depth-first searchHeaps and priority queues

01Why it matters

Every sat-nav asks this question

What is the shortest route from A to F, when roads have different lengths? Breadth-first search answers it when every road is the same length, because it explores in rings of "one step away", "two steps away"… With lengths, the nearest node is no longer the one with the fewest steps.

Dijkstra's idea is to keep exploring in rings, but rings of distance: always handle the closest node you haven't finished yet. Once a node is the closest unfinished one, nothing can ever give it a shorter route, so you can settle it for good.

02Key parts

The pieces you will see

dist[v]
The best distance from the start to v found so far. Starts at ∞ for everything except the start (0).
settled
A node whose distance is final. Each node is settled exactly once.
relaxation
Checking an edge u → v: if dist[u] + w beats dist[v], update dist[v] and remember u as v's predecessor.
min-heap
A priority queue that hands back the unsettled node with the smallest tentative distance.

03See it work

Watch the distances settle

Nodes are settled in increasing order of distance: 0, 2, 3, 8, 10, 13. At the end, following prev from F gives the route.

Watch the heap panel: a node can be pushed several times as its distance improves. The older, larger entries become stale and are skipped when popped. That "lazy" approach is simpler than updating entries in place.

04Predict

Your turn: settle and relax

Predict which node is settled next and whether each edge improves a distance.

Make 6 predictions: step forward and answer each question before the next step plays.

0 of 6 made

05Try it

Break the assumption

Pick the graph with a negative edge. Dijkstra settles B at distance 2 straight away, before discovering that going through C would cost 5 − 4 = 1. The visualiser finishes, then checks the true distances and names the ones it got wrong.

One negative edge is enough to make settling too early wrong.

06Check yourself

Check yourself

  1. Question 1 of 5

    Which node does Dijkstra settle next?

    Your answer comes back in Review in a few days, so it sticks.

  2. Question 2 of 5

    dist[C] = 7 and an edge B → C has weight 2, with dist[B] = 4. What does relaxing the edge do?

  3. Question 3 of 5

    Why can Dijkstra give wrong answers with a negative edge?

  4. Question 4 of 5

    With a binary heap, about how long does Dijkstra take on V nodes and E edges?

  5. Question 5 of 5

    A graph has one edge of weight −3 and no negative cycle. Does Dijkstra always find the shortest distances?

07Explain it back

Say it in your own words

How does Dijkstra’s algorithm choose which node to settle next, and why is that node’s distance final?

08Recap

What to remember

  • Dijkstra settles nodes in increasing order of distance, relaxing each settled node's edges.
  • A min-heap finds the closest unsettled node in O(log V); stale entries are skipped.
  • It is correct only without negative edges; Bellman–Ford handles those.
  • For every pair at once, all-pairs shortest paths runs Floyd–Warshall.
  • It is breadth-first search with "rings of distance" instead of "rings of steps", and the basis of routing and A* search.
Back to path