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

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:

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 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 \}$$.