プリム法

プリム法は、最小全域木を求める貪欲法ベースで時間計算量がO(E+V log V)となる探索アルゴリズム.(最小全域木は、エッジに重みがついている連結グラフで全ての点を最小のコストで結ぶ木) 時間計算量は実装方法に依存する. アルゴリズムは非常にシンプルで、 特定の点から始めて常に繋がりうるエッジのうち最小のコストのエッジを選択することを繰り返す. アルゴリズム 適当に選んだ点を一つ含んだ頂点リストVと 初めは空であるエッジリストEを用意 1. 現在のVのリストの中から次に結ぶことのできる点vとエッジeから最小コストになるものを選択 2. vをVに追加 3. eをEに追加 4. 上記を全点が含まれるまで繰り返す.

上記の最小コストのエッジを選択し続けることで本当に全体においても最適になっているかは背理法で示すことができる. 仮にエッジの選択を誤っていてよりコストの少ない経路で結ばれているとすると、aとcは直接ではなく別の点を中継して経路で結ばれていることになります.しかしエッジに負の経路はなくaからc以外への経路は常にaからcのコストを上回るため、よりコストの少ない経路は存在できません. そのためエッジの選択は正しいとわかります.