How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

Question

In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by Dijkstra's algorithm. However, he also poses another problem, namely that of constructing the tree of minimum total length between the $n$ nodes of the connected graph.

I am a bit unsure as to what this exactly means, so I tried performing the algorithm but in step 2 one needs to compare the branch (or edge) under consideration to the 'corresponding' branch in set II. It is however not clear to me what this corresponding branch is supposed to be. It also seems to me that at some point in the algorithm one needs to add branches to set II, but it is not clearly described when this happens.

So my question is how does this algorithm work exactly and what precisely does it output?

Below you can find the algorithm in image form:

Answer 1

In modern terms, this problem is called Minimum Spanning Tree: Find the subtree of the input graph that minimizes the total weight of its edges. The algorithm here suggested by Dijkstra is today known as Prim's algorithm.

Regarding your question, the "corresponding branch" to a node $b$ in set $B$ is the shortest edge that runs from some node that was put into set $A$ at an earlier step, to $b$. There might well be no such edge; in that case you should clearly put your new edge into set II.

Answer 2

The tree of minimum total length is nothing but the minimum spanning tree. The algorithm that you are talking about is nothing but Prim's algorithm, also called Prim–Dijkstra algorithm.

Answer to Your Question: The corresponding branch is defined for every vertex $v \in B$. It is the minimum weighted edge among the edges that are incident on $v$ and set $A$. That is minimum weight edge among the edge set: $E_{v} = \{(u,v) \mid u \in A \}$.