A Note on Two Problems in Connexion with Graphs

グラフに関連する二つの問題についての覚え書き

By

E. W. DIJKSTRA

$n$ 個の点（ノード）を考える。そのいくつかまたはすべての対は分岐によって接続されており、各分岐の長さは与えられている。任意の二つのノード間に少なくとも一つの経路が存在する場合に限定する。ここで二つの問題を考える。

問題 1. $n$ 個のノード間における全長が最小の木を構成せよ。（木とは、任意の二つのノード間に一つだけの経路をもつグラフである。）

ここで提示する構成の過程において、分岐は三つの集合に分割される。

I. 構成中の木に確定的に割り当てられた分岐（これらは部分木を形成する）；

II. 集合 I に次に追加される分岐を選択する元となる分岐；

III. 残りの分岐（棄却されたもの、またはまだ考慮されていないもの）。

ノードは二つの集合に分割される：

A. 集合 I の分岐によって接続されたノード、

B. 残りのノード（集合 II の一つかつ唯一の分岐が、これらの各ノードへ向かう）。

構成は、集合 A の唯一のメンバーとして任意の一つのノードを選択し、このノードで終わるすべての分岐を集合 II に入れることによって開始する。開始時には、集合 I は空である。それ以後、次の二つのステップを繰り返し実行する。

ステップ 1. 集合 II の最短の分岐をこの集合から取り除き、集合 I に追加する。