唯一の SSSP アルゴリズム

グラフの探索問題や最小全域木問題と同じように、多くの異なる SSSP アルゴリズムは次に示す一般的なアルゴリズムの特殊ケースとして表現できます。このアルゴリズムは Lester Ford (レスター・フォード) によって 1956 年に、そして Geroge Dantzig (ジョージ・ダンツィグ) によって 1957 年に、George Minty (ジョージ・ミンティ) によって 1958 年にそれぞれ独立に発見されました1。このアルゴリズムではグラフの各頂点 (v) が次の二つの値を保存し、これらの値によって (s) から (v) への暫定的な最短路が表されます:

前者へのポインタ \(\mathit{pred}(s)\) によって \(s\) を根とする暫定的な木が自動的に定義されます。このポインタは一般的なグラフ走査アルゴリズムにおける親へのポインタとちょうど同じものです。アルゴリズムは各頂点の距離と前者を初期化する次の処理から始まります:

procedure \(\texttt{InitSSSP}\)(\(s\))

\(\mathit{dist}(s) \leftarrow 0\)

\(\mathit{pred}(s) \leftarrow \textsc{Null}\)

for 頂点 \(v \neq s\) do

\(\mathit{dist}(v) \leftarrow \infty\)

\(\mathit{pred}(v) \leftarrow \textsc{Null}\)

アルゴリズムの実行中に辺 \(u \rightarrow v\) が \(\mathit{dist}(u) + w(u \rightarrow v) < \mathit{dist}(v)\) を満たすとき、\(u \rightarrow v\) は緊張 (tense) していると言います。辺 \(u \rightarrow v\) が緊張しているとき \(s \rightsquigarrow u \rightarrow v\) の方が \(s \rightsquigarrow v\) よりも短いので、暫定的な最短路 \(s \rightsquigarrow v\) が正しくないことが明らかです。このとき次のように辺を緩和 (relax) することで、この明らかな過大評価を訂正 (正確には改善) できます:

procedure \(\texttt{Relax}\)(\(u \rightarrow v\))

\(\mathit{dist}(v) \leftarrow \mathit{dist}(u) + w(u \rightarrow v)\)

\(\mathit{pred}(v) \leftarrow u\)

ここまで説明すれば、Ford の一般的なアルゴリズムは一行で簡単に説明できます:

緊張した辺が無くなるまで緊張した辺を繰り返し緩和する

procedure \(\texttt{FordSSSP}\)(\(s\))

\(\texttt{InitSSSP}\)(\(s\))

while 緊張した辺が一つ以上ある do

緊張した辺を適当に選んで緩和する

\(\textsc{FordSSSP}\) が停止したときには緊張した辺が存在しないので、各頂点 \(v\) から前者 \(\mathit{pred}(v)\) へのポインタの集合が最短路木を正しく定義し、\(\mathit{dist}(v)\) が \(s\) から \(v\) への最短路の実際の長さとなります。また \(s\) から \(v\) に到達できないときには \(\mathit{dist}(v) = \infty\) であり、グラフが \(s\) から到達できる負閉路を含むときにはアルゴリズムは停止しません。

この Ford の一般的なアルゴリズムの正しさは次の簡単な命題から従います:

  1. アルゴリズムの実行中の任意の時点で、任意の頂点 \(v\) に対する距離 \(\mathit{dist}(v)\) は \(\infty\) であるか、そうでなければ \(s\) から \(v\) へのある歩道の長さである。このことは緩和の回数に関する帰納法によって示せる。

  2. グラフに負閉路が含まれない場合、任意の頂点 \(v\) に対して \(\mathit{dist}(v)\) は \(\infty\) であるか、そうでなければ \(s\) から \(v\) へのある単純路の長さである。またもし \(\mathit{dist}(v)\) が \(s\) から \(v\) への閉路を含む歩道の長さであった場合、その閉路は負の長さを持っている。\(G\) の単純路は有限しかないので、\(G\) に負閉路が含まれないならば緩和アルゴリズムはいずれ停止することが分かる。

  3. \(G\) に緊張した辺が無いならば、任意の頂点 \(v\) に対して \(\mathit{dist}(v)\) は前者をたどった路 \(s \rightarrow \cdots\) \(\mathit{pred}(\mathit{pred}(v))\) \(\rightarrow \mathit{pred}(v)\) \(\rightarrow v\) の長さと等しい。なぜなら、もしある頂点 \(v\) がこの条件を満たさないなら辺 \(\mathit{pred}(v) \rightarrow v\) が緊張しているからである。

  4. \(G\) に緊張した辺が無いならば、任意の頂点 \(v\) に対して前者をたどった路 \(s \rightarrow \cdots\) \(\mathit{pred}(\mathit{pred}(v)) \rightarrow \mathit{pred}(v) \rightarrow v\) が実は \(s\) から \(v\) への最短路である。なぜなら、もしある頂点 \(v\) がこの条件を満たさず、かつ本当の最短路における \(v\) の前者 \(u\) がこの条件を満たしているとき、辺 \(u \rightarrow v\) が緊張しているからである。この命題によってもし \(G\) が負閉路を含むならば緊張している辺が常に存在し、したがってこのアルゴリズムが停止しないことが分かる。

緊張している辺をどうやって見つけるか、あるいは緊張している辺が複数あるときにどうやって緩和する辺を選ぶかについてはこれまでに話してきませんでした。グラフ走査アルゴリズムと同じように、Ford の一般的な緩和アルゴリズムにもいくつかの異なるインスタンスが存在します。しかしグラフ走査アルゴリズムと違って、それぞれの探索戦術の正しさと効率の良さは入力グラフの構造に依存します。

この章の残りでは、Ford のアルゴリズムの最もよく知られた四つのインスタンスについて議論します。それぞれのアルゴリズムは異なるグラフのクラスに対する最適な選択肢です。一般的な正しさの証明の残りの詳細は練習問題に回して、代わりに (もっと有益な) 具体的な四つのアルゴリズムに対する正しさの証明を見ていくことにします。

  1. 正確に言うと、Danzig は最短路問題が線形計画問題として表現できることを示し、それから彼が考案した単体法を元のグラフの言葉を使って説明しました。彼の説明は Ford の緩和を使った戦略と (事実上) 同じです。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。