A Note on Two Problems in Connexion with Graphs

Một ghi chú về hai bài toán liên quan đến đồ thị

Bởi

E. W. DIJKSTRA

Xét $n$ điểm (nút), một số hoặc tất cả các cặp trong số chúng được nối với nhau bởi một nhánh; độ dài của mỗi nhánh được cho trước. Chúng ta chỉ xét trường hợp trong đó tồn tại ít nhất một đường đi giữa bất kỳ hai nút nào. Bây giờ chúng ta xét hai bài toán.

Bài toán 1. Xây dựng cây có tổng độ dài nhỏ nhất giữa $n$ nút. (Một cây là một đồ thị có một và chỉ một đường đi giữa mỗi hai nút.)

Trong quá trình xây dựng mà chúng ta trình bày ở đây, các nhánh được chia thành ba tập:

I. các nhánh chắc chắn được gán cho cây đang được xây dựng (chúng sẽ tạo thành một cây con);

II. các nhánh mà từ đó nhánh tiếp theo được thêm vào tập I sẽ được chọn;

III. các nhánh còn lại (bị loại bỏ hoặc chưa được xét đến).

Các nút được chia thành hai tập:

A. các nút được nối bởi các nhánh của tập I,

B. các nút còn lại (một và chỉ một nhánh của tập II sẽ dẫn đến mỗi nút này).

Chúng ta bắt đầu việc xây dựng bằng cách chọn một nút tùy ý làm thành viên duy nhất của tập A, và đặt tất cả các nhánh kết thúc tại nút này vào tập II. Ban đầu, tập I là rỗng. Từ đó trở đi, chúng ta lặp lại hai bước sau.

Bước 1. Nhánh ngắn nhất của tập II được lấy ra khỏi tập này và thêm vào tập I.

By E. W. DIJKSTRA

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. Construct 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 assigned 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 set I. As a result one node is transferred from set $B$ to set $A$.

Step 2. Consider the branches leading from the node, that has just been transferred to set A, to the nodes that are still in set B. If the branch under consideration is longer than the corresponding branch in set II, it is rejected; if it is shorter, it replaces the corresponding branch in set II, and the latter is rejected.

We then return to step 1 and repeat the process until sets II and B are empty. The branches in set I form the tree required.

The solution given here is to be preferred to the solution given by J. B. KRUSKAL [1] and those given by H. LOBERMAN and A. WEINBERGER [2]. In their solutions all the — possibly $\frac{1}{2} n(n-1)$ — branches are first of all sorted according to length. Even if the length of the branches is a computable function of the node coordinates, their methods demand that data for all branches are stored simultaneously. Our method only requires the simultaneous storing of the data for at most $n$ branches, viz. the branches in sets I and II and the branch under consideration in step 2.

Problem 2. Find the path of minimum total length between two given nodes $P$ and $Q$.

We use the fact that, if $R$ is a node on the minimal path from $P$ to $Q$, knowledge of the latter implies the knowledge of the minimal path from $P$ to $R$. In the solution presented, the minimal paths from $P$ to the other nodes are constructed in order of increasing length until $Q$ is reached.

In the course of the solution the nodes are subdivided into three sets: A. the nodes for which the path of minimum length from $P$ is known; nodes will be added to this set in order of increasing minimum path length from node $P$; B. the nodes from which the next node to be added to set A will be selected; this set comprises all those nodes that are connected to at least one node of set A but do not yet belong to A themselves; C. the remaining nodes.

The branches are also subdivided into three sets: I. the branches occurring in the minimal paths from node $P$ to the nodes in set A; II. the branches from which the next branch to be placed in set I will be selected; one and only one branch of this set will lead to each node in set B; III. the remaining branches (rejected or not yet considered).

To start with, all nodes are in set C and all branches are in set III. We now transfer node $P$ to set A and from then onwards repeatedly perform the following steps.

Step 1. Consider all branches $r$ connecting the node just transferred to set A with nodes $R$ in sets B or C. If node $R$ belongs to set B, we investigate whether the use of branch $r$ gives rise to a shorter path from $P$ to $R$ than the known path that uses the corresponding branch in set II. If this is not so, branch $r$ is rejected; if, however, use of branch $r$ results in a shorter connexion between $P$ and $R$ than hitherto obtained, it replaces the corresponding branch in set II and the latter is rejected. If the node $R$ belongs to set C, it is added to set B and branch $r$ is added to set II.

Step 2. Every node in set B can be connected to node $P$ in only one way if we restrict ourselves to branches from set I and one from set II. In this sense each node in set B has a distance from node $P$: the node with minimum distance from $P$ is transferred from set B to set A, and the corresponding branch is transferred from set II to set I. We then return to step 1 and repeat the process until node $Q$ is transferred to set A. Then the solution has been found.

Remark 1. The above process can also be applied in the case where the length of a branch depends on the direction in which it is traversed.

Remark 2. For each branch in sets I and II it is advisable to record its two nodes (in order of increasing distance from $P$), and the distance between $P$ and that node of the branch that is furthest from $P$. For the branches of set I this is the actual minimum distance, for the branches of set II it is only the minimum thus far obtained.

The solution given above is to be preferred to the solution by L. R. Ford [3] as described by C. Berge [4], for, irrespective of the number of branches, we need not store the data for all branches simultaneously but only those for the branches in sets I and II, and this number is always less than $n$. Furthermore, the amount of work to be done seems to be considerably less.