The setting is a connected weighted graph. Dijkstra calls vertices “nodes”, edges “branches” and weights “lengths”. Some or all pairs of nodes may be connected, and at least one path exists between every pair. Problem 1 seeks a tree spanning all n nodes with minimum total branch length. Problem 2 seeks a path of minimum total length between P and Q.

The two objectives must not be confused. A minimum spanning tree minimises the sum of edges needed to connect everybody; it need not contain the shortest route between any chosen pair. A shortest-path tree records individually shortest routes from one source; its total edge weight need not be the minimum possible connection network. Dijkstra places them together because their constructions share a frontier discipline, not because they solve the same optimisation.

For each problem, some objects are permanent, some are candidates and the rest are unconsidered or rejected. A candidate is not merely “nearby”. It carries the best currently known connexion to a permanent structure. When new information produces a shorter candidate for the same outside node, replacement is immediate. The smallest candidate is then promoted.

That promotion is the intellectual centre. Greedy procedures can be plausible and wrong: a locally short edge might foreclose a better global solution. Here permanence is justified by an invariant. In the spanning-tree problem, the lightest edge crossing the current cut is safe. In the route problem, the smallest tentative distance is final when lengths cannot become negative along a later detour. The paper states the constructions compactly; modern proofs expose why their choices are safe.

A path is a sequence of incident branches. Its length is the sum of their lengths. A tree is defined operationally as a graph with exactly one path between each pair of nodes. A spanning tree therefore uses enough branches to connect all n nodes without a cycle; any such tree has n−1 branches. The input graph itself may contain up to n(n−1)/2 undirected branches.

Dijkstra assumes connectedness explicitly. If the graph were disconnected, no tree could span every node and some P-to-Q routes would be absent. A modern implementation can return a minimum spanning forest or infinity for unreachable vertices, but those are extensions. His stopping conditions presuppose that the candidate frontier will keep supplying a next node.

The note calls weights lengths and never discusses negative numbers. Physical length is naturally non-negative. The spanning-tree procedure actually tolerates negative edge weights because its cut argument compares weights without accumulating routes. The shortest-path procedure does not: once a node is declared final, a later path containing a negative edge could make it cheaper. Distinguishing the paper’s language from the modern formal precondition avoids attributing an unstated algebraic theorem to three historical pages.

Dijkstra’s first remark says the route process also applies when branch length depends on traversal direction. That is a directed graph in modern language: w(u,v) may differ from w(v,u). The spanning-tree problem was framed with undirected connexions; directed minimum arborescences are a different problem. One short remark extends Problem 2, not both procedures indiscriminately.

Choose any starting node as the sole member of A. Set I is empty. For every outside node directly joined to the start, put its incident branch into II; if the graph is understood through all pairwise computable lengths, each outside node immediately receives one candidate. The candidate represents that node’s cheapest known way to attach to the current subtree.

Step 1 removes the shortest candidate branch from II and makes it permanent in I. Its outside endpoint moves from B to A. Step 2 scans branches from the newly admitted node to nodes still in B. If a scanned branch is longer than that node’s candidate, reject it. If shorter, replace the old candidate and reject the old branch. Then choose the shortest candidate again.

Because every permanent branch introduces exactly one outside node, the permanent edges cannot make a cycle. Connectivity grows by one node per promotion. When B and II are empty, I contains n−1 branches connecting every node: a spanning tree. Ties can produce different trees with the same minimum total length; the procedure need not specify a unique answer.

This is now commonly called Prim’s algorithm, after R. C. Prim’s 1957 paper, although related versions predate both Prim and Dijkstra. Historical naming should not erase the primary’s actual contribution: Dijkstra presents the construction independently, compares its storage with Kruskal and Loberman–Weinberger, and places it beside his shortest-path procedure as a shared frontier pattern.

Let A be the currently connected nodes and choose the minimum-weight branch e crossing from A to V\A. Consider any minimum spanning tree T. If T contains e, the promotion is already compatible with an optimum. If not, add e to T. A cycle appears because T already contains a unique path between e’s endpoints.

That cycle must cross the cut somewhere else, through an edge f. Since e is the lightest crossing edge, w(e)≤w(f). Remove f. The result remains a spanning tree and costs no more than T. Because T was minimum, the exchanged tree is also minimum and now contains e. Thus every promotion can be extended to at least one globally optimal tree.

The proof is an exchange argument, not a claim that the smallest edge anywhere is always safe. Only an edge crossing the cut defined by the existing subtree is eligible. Choosing a tiny edge between two outside nodes could create a separate component and would no longer match Dijkstra’s set invariant, though another algorithm such as Kruskal can safely order edges under a different forest invariant.

Candidate replacement ensures the algorithm actually finds the lightest crossing edge without retaining all of them. For each outside node, any non-minimum attachment to A can never win while its cheaper attachment remains. Taking the minimum over these per-node minima therefore equals taking the minimum over the entire cut. Compression preserves the decision-relevant statistic.

Kruskal’s procedure sorts all edges by length, then scans them from shortest upwards, accepting an edge if it connects two different components. In a dense n-node graph there may be n(n−1)/2 edges. Dijkstra argues that sorting and storing all those branches is unnecessary when edge lengths can be computed from node coordinates or otherwise produced as needed.

His frontier representation keeps n−1 or fewer permanent and candidate branches: permanent edges connect the current subtree, while each outside node owns one candidate. When an examined edge cannot improve that node’s attachment, it can be forgotten. The claim concerns simultaneous branch records under a particular access model, not the total number of edge comparisons. A dense graph may still require many lengths to be computed over the entire run.

Modern complexity statements depend on representation. With an adjacency matrix and a linear scan for the minimum key, the spanning-tree procedure takes O(n²) time and O(n) extra frontier storage beyond the matrix. With adjacency lists and a binary heap it takes O((|V|+|E|)log|V|), often written O(|E|log|V|) for connected graphs. A Fibonacci heap gives the classical O(|E|+|V|log|V|) bound. None of this notation appears in the 1959 note.

The historical lesson is more durable than a single asymptotic bound. An algorithm is a policy for information retention. The candidate array is a sufficient summary of every processed crossing edge: only the cheapest attachment per outside node can affect the next choice. Dijkstra’s data structures are therefore part of the proof, not an implementation afterthought.

Suppose a minimum P-to-Q path reaches R along a prefix that is not minimum. Replace that prefix with a shorter P-to-R path and retain the remaining suffix from R to Q. The combined route would be shorter than the alleged minimum, a contradiction. This optimal-substructure argument justifies recording one predecessor for each best-known route.

The fact alone does not say which prefix becomes known next. Dijkstra constructs minimal routes from P to other nodes in increasing total length until Q is reached. A node becomes permanent only when its tentative distance is the smallest among all frontier nodes. The distance label, not a single edge length, orders the route frontier.

This distinction separates Problems 1 and 2. The spanning-tree key of an outside node is the cheapest edge connecting it to the tree. The route key is the cheapest total distance from P through already permanent nodes plus one frontier edge. Both records have a parent pointer, but one optimises a network attachment and the other an accumulated source-relative path.

Modern presentations call the update “relaxation”. For a permanent node u and neighbour v, compare the current tentative d[v] with d[u]+w(u,v). If the new route is shorter, replace both distance and predecessor. Dijkstra describes the same operation in prose: the corresponding branch in candidate set II is replaced, and the old branch rejected.

Branches again occupy sets I, II and III. Set I contains branches forming the permanent minimum paths from P to nodes in A. Set II contains exactly one candidate predecessor branch for each node in B. Set III holds rejected or unexamined branches. Each candidate carries the total distance from P to its farther endpoint, not merely its own branch length.

Initially every node is in C and every branch in III. Transfer P to A with distance zero. Step 1 examines every branch from the newly permanent node to nodes in B or C. A C neighbour enters B with its branch in II. A B neighbour receives the new route only if it is shorter than the route represented by its current candidate.

Step 2 selects the B node with minimum tentative distance, transfers it to A and transfers its candidate branch from II to I. Then Step 1 relaxes the new node’s outgoing branches. Repeat until Q enters A. Stopping at Q is correct because its distance is final on promotion; continuing would construct shortest paths from P to every reachable node.

The predecessor pointers in I form a rooted tree over settled nodes. If several shortest routes tie, the chosen tree depends on tie-breaking even though every recorded distance is correct. Dijkstra’s second remark advises storing each I or II branch with endpoints ordered by increasing distance from P and with the distance to the farther endpoint. That record is recognisably the modern pair parent[v], d[v].

Take a genuinely shortest path from P to u. If it stays inside A until its final edge, relaxation from the last permanent predecessor has already offered its exact length to u. Otherwise let y be the first node on that path outside A and x its permanent predecessor. When x was settled, edge x–y was relaxed, so d[y] is at most the true shortest distance to y.

Non-negative remaining lengths imply δ(P,y)≤δ(P,u): travelling further along the path cannot reduce its accumulated length. Since u was chosen as the smallest tentative node, d[u]≤d[y]. Tentative labels are lengths of actual discovered routes, so δ(P,u)≤d[u]. Chaining the inequalities forces equality. The promoted label is the true minimum.

A negative branch breaks the middle inequality. A route can travel to a currently expensive node, then use a negative edge to become cheaper than an already settled node. The procedure can still work on special graphs containing negative edges, but the simple general guarantee is gone. Bellman–Ford’s repeated relaxation or a valid reweighting method is needed for the broader problem.

Zero-length branches are harmless: they create ties, not reversals. Directed non-negative weights are also harmless, exactly as Dijkstra’s first remark anticipates, provided Step 1 scans outgoing branches in their traversal direction. The proof relies on non-decreasing path length, not on symmetry.

An adjacency matrix plus a linear scan produces the familiar O(|V|²) implementation. An adjacency list with a binary heap gives O((|V|+|E|)log|V|); for a connected graph this is commonly simplified to O(|E|log|V|). Decrease-key heaps and specialised integer queues yield other bounds. Those are later engineering refinements, not retroactive details of the three-page primary.

A common implementation pushes a fresh heap entry whenever a tentative distance improves rather than decreasing an existing key. Stale entries are skipped when popped. This may store more than one heap record per frontier node, departing from the primary’s literal one-branch set II, but it implements the same mathematical relaxation if stale records never settle a vertex twice.

Arithmetic belongs inside the contract. Infinity plus a weight must not overflow to a small number; finite integer sums must fit their type; floating-point ties need a declared tolerance only if weights are approximate measurements. A proof over real lengths does not certify a machine implementation whose comparison order is corrupted by overflow or NaN.

The route procedure finds a shortest walk under non-negative weights and can stop at Q. It does not solve longest paths, enumerate all equally short paths, optimise several incomparable costs or handle time-dependent weights without additional assumptions. The tree procedure does not preserve pairwise shortest routes. Naming these boundaries is part of using the algorithms correctly.

In Problem 1, key[v] measures the cheapest single edge attaching v to the current tree. The proof uses an exchange across a cut. In Problem 2, d[v] measures the cheapest accumulated route from P whose internal nodes are settled. The proof uses optimal prefixes and non-negative continuation. Writing both as “choose the nearest node” erases the quantity being minimised.

The note’s compactness also reveals a style of algorithm design. Partition knowledge into settled, tentative and unseen. State exactly what one tentative record means. Update only from the object just settled. Promote only when an invariant converts tentative into irrevocable. Stop when the objective is certified, not merely encountered.

Dijkstra claims storage advantages over the compared methods and says the amount of work “seems” considerably less than Ford’s described solution. That is an historically faithful qualitative claim, not a proved modern complexity comparison. Later analysis, data structures and graph models are needed to translate it into asymptotic bounds.

Nothing in the note establishes general agency or intelligence. The procedures have a fixed objective, complete access to declared edge lengths and no learning or preference formation. Their importance for formal agency is architectural: a goal-directed search can act locally without losing global correctness when its state summary and permanence proof are exact.