Skip to content
A Note on Two Problems in Connexion with Graphs 4 min

Edsger W. Dijkstra · Numerische Mathematik 1959

A Note on Two Problems in Connexion with Graphs

Dijkstra's three page 1959 note: settle nodes in order of distance and a shortest path falls out. Step through the method on a small road map.

Read the original paper

Algorithms · White Belt · Pro · 4 min read

A Note on Two Problems in Connexion with Graphs

How does a map app find the quickest way home? Behind the blue line is a graph: places are dots, roads are lines, and each road has a length. The task is to find the shortest chain of roads between two places. In 1959 Edsger Dijkstra published a three page note that solves it with a method so natural that we still teach it today.

His note, only three pages, treats two problems on a network of points joined by branches of known length. The first is to connect all the points with the least total length of branches. The second is to find the shortest path between two given points. The second one made him famous, and it is the one we follow here.

Dijkstra's method finds shortest paths by settling nodes in order of distance. Keep the best known distance to every node. Repeatedly take the closest node you have not finished, lock in its distance, and check whether it offers a shorter way to its neighbors. It works because branch lengths are never negative.

Three groups of nodes

Dijkstra describes the work with three sets of nodes. Start by choosing the node P you travel from.

  • Set A: nodes whose shortest path from P is already known. Only P is here at the start.
  • Set B: nodes joined by a branch to some node of A, so we have a route to them, but maybe not yet the shortest.
  • Set C: every other node.
Dijkstra's three sets of nodes. Set A holds nodes whose shortest distance is settled. Set B holds nodes reachable from A by one branch. Set C holds the rest. The closest node in B always joins A next.

Each round has two steps. First, look at the branches from the node that just joined A. If one gives a shorter route to a node in B, or reaches a node in C for the first time, record it. Second, pick the node in B with the smallest distance and move it into A.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

3 more sections, 1 more diagram and 2 interactive elements to play with

  • Why the closest candidate is final
  • Run it yourself
  • How fast, and where it is used

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.