A note on two problems in connexion with graphs
A note on two problems in connexion with graphs
复制标题
DOI：
10.1145/3544585.3544600
复制
发表时间：
1959-12
影响因子：
2.1
通讯作者：
E. Dijkstra
中科院分区：
文献类型：
--
作者：
E. Dijkstra
我们考虑n个点（节点），其中一些或所有对由分支连接；给出每个分支的长度。我们将自己限制在任何两个节点之间至少存在一条路径的情况下。我们现在考虑两个问题。问题1。约束n个节点之间最小总长度的树。 （一棵树是一个图形，在每个两个节点之间有一个，只有一个路径。）在我们在这里提出的构造过程中，分支被细分为三组：I。分支绝对分配给正在建造的树（他们将形成一个子树）； ii。将选择要添加到集合I的下一个分支的分支； iii。其余的分支（被拒绝或尚未考虑）。节点被细分为两组：A。由集合I，B的分支连接的节点。其余的节点（集合II的一个和仅一个分支II的一个分支将导致这些节点中的每个节点），我们通过选择一个来开始构造任意节点是集合A的唯一成员，并通过将所有分支放置在集合II中的该节点中结束。首先，设置我为空。从那时起，我们反复执行以下两个步骤。步骤1。集合II的最短分支从此集合中删除，并添加到
We consider n points (nodes), some or all pairs of which are connected by a branch; the length of each branch is given. We restrict ourselves to the case where at least one path exists between any two nodes. We now consider two problems. Problem 1. Constrnct the tree of minimum total length between the n nodes. (A tree is a graph with one and only one path between every two nodes.) In the course of the construction that we present here, the branches are subdivided into three sets: I. the branches definitely assignec~ to the tree under construction (they will form a subtree) ; II. the branches from which the next branch to be added to set I, will be selected ; III. the remaining branches (rejected or not yet considered). The nodes are subdivided into two sets: A. the nodes connected by the branches of set I, B. the remaining nodes (one and only one branch of set II will lead to each of these nodes), We start the construction by choosing an arbitrary node as the only member of set A, and by placing all branches that end in this node in set II. To start with, set I is empty. From then onwards we perform the following two steps repeatedly. Step 1. The shortest branch of set II is removed from this set and added to