关于图的两个问题的一点注记
作者
E. W. DIJKSTRA
我们考虑个点（节点），其中某些或所有点对由一条分支连接；每条分支的长度均已给定。我们限于考虑任意两个节点之间至少存在一条路径的情形。现在考虑两个问题。
问题1。构造连接这个节点且总长度最小的树。（树是这样一种图：任意两个节点之间有且仅有一条路径。）
在我们这里给出的构造过程中，将分支划分为三个集合：
I. 确定归入正在构造的树中的分支（它们将构成一个子树）；
II. 将从中选取下一条加入集合I的分支的分支；
III. 其余分支（已拒绝或尚未考虑）。
将节点划分为两个集合：
A. 由集合I中的分支连接的节点，
B. 其余节点（集合II中恰有一条分支通向这些节点中的每一个）。
我们首先任意选择一个节点作为集合A的唯一成员，并将所有终止于该节点的分支置于集合II中。开始时，集合I为空。此后，我们反复执行以下两个步骤。
步骤1。从集合II中移除最短的分支，并将其加入集合I。