Essay: A Note on Two Problems in Connexion with Graphs

Overview
Edsger Dijkstra’s 1959 note introduces two fundamental graph problems and presents simple, efficient greedy algorithms to solve them. The first is the single-source shortest path problem in a graph with non-negative edge lengths. The second is constructing a spanning tree that connects all vertices with minimum total length. Both algorithms proceed by growing a set of vertices or edges in stages, each stage making a locally optimal choice that can be proved globally optimal.

Single-source shortest paths
Given a graph with non-negative edge lengths and a designated source vertex, the task is to determine the shortest distance from the source to every other vertex and, if desired, the corresponding paths. Dijkstra assigns a tentative label to each vertex: zero for the source, infinity for all others. Repeatedly, he selects the not-yet-finalized vertex with the smallest tentative label, declares that label final, and relaxes outgoing edges from it by lowering neighbors’ tentative labels when a shorter route is discovered through the selected vertex. Recording the predecessor that yields each improvement recovers shortest paths.

Correctness insight
The key invariant is that once a vertex is selected as having the smallest tentative label among all unsettled vertices, its label equals the true shortest distance. This follows from non-negativity: any alternative route to that vertex would have to pass through an unsettled vertex whose tentative label cannot be smaller, so no shorter path exists. Inductively, each selection is safe, and the process yields correct distances for all vertices. The algorithm terminates after each vertex has received a final label, at which point the predecessors form a shortest-path tree rooted at the source.

Minimum spanning tree
The second problem asks for a subset of edges connecting all vertices with minimum total length, assuming an undirected, connected graph. Dijkstra describes a method that starts from any vertex and grows a tree one edge at a time. At each step it chooses, among all edges with exactly one endpoint in the current tree, the edge of minimum length, adding its outside endpoint and that edge to the tree. Repeating this until all vertices are included yields a spanning tree of minimum weight.

Correctness insight
The safety of each greedy choice rests on an exchange argument: if a minimum spanning tree did not contain the chosen minimum-length crossing edge, adding it would form a cycle that must contain some other edge crossing the same cut; replacing that longer edge with the chosen edge produces a spanning tree no heavier than the original. Hence there exists an optimal tree containing every chosen edge, and the final tree is optimal.

Complexity and implementation
Both methods are conceptually simple and efficient for the hardware and software of the time. Using arrays for tentative labels and a linear search to select the smallest label, the shortest path algorithm requires roughly quadratic time in the number of vertices, as does the spanning tree algorithm when selecting the lightest edge crossing the cut by scanning. The shortest path method crucially relies on non-negative lengths; negative edges would invalidate the selection rule. Both algorithms can construct the associated trees by recording predecessors or chosen edges as they proceed.

Impact
The note crystallized two archetypal greedy strategies, each justified by a clean invariant or exchange argument, and provided practical procedures for routing and network design. The shortest path algorithm and the minimum spanning tree algorithm have become standard tools across computer science, operations research, and communications, valued for their clarity, efficiency, and ease of implementation.