## Dijkstra’s algorithm

16 Apr 2009, 15:34 UTCDijkstra’s algorithm for finding the shortest paths in a graph is a classical one that most students of computer science get to learn about, although I suspect few have actually read the original paper. Published in the very first volume of the journal Numerische Mathematik in 1959, an official copy of the three-page paper A Note on Two Problems in Connexion with Graphs is available from SpringerLink, although you would have to be at an academic institution with a subscription or have a personal subscription to SpringerLink to download the paper.

The problems

As the title of the paper suggests, the paper puts forward two similar algorithms for two related but distinct problems. In Edsger Dijkstra’s own words:

We consider multiple nodes, some or all pairs of which are connected by a branch; the length of each branch is given. We restrict ourselves to the case where at least one path exists between any two nodes. We now consider two problems.

Construct the tree of minimum total length between nodes.

Find the path of minimum total length between two given nodes.

The first problem is the minimum spanning tree problem. No one calls the algorithm that Dijkstra suggested for finding ...