導入
前章では単一の頂点 \(s\) から他の全ての頂点への最短路を \(s\) を根とした最短路木を作ることで見つけるアルゴリズムについて議論しました。最短路木はグラフの各頂点 \(v\) に対して二つの情報を割り当てます:
-
\(s\) から \(v\) への最短路の長さを表す \(\mathit{dist}(v)\)
-
\(s\) から \(v\) への最短路における最後から二つ目の頂点を表す \(\mathit{pred}(v)\)
この章で扱うのは、もっと一般的な全組最短路問題 (all pairs shortest path problem, APSP) です。これは任意のソース頂点から任意の目標頂点への最短路を求める問題であり、この問題を解くアルゴリズムは \(G\) の全ての頂点の組 \(u, v\) に対して次の情報を計算します:
-
\(u\) から \(v\) への最短路の長さを表す \(\mathit{dist}(u, v)\)
-
\(u\) から \(v\) への最短路における最後から二つ目の頂点を表す \(\mathit{pred}(u, v)\)
この直感的な定義は二つの例外的なケースをいくつか無視していますが、どれも前章で見たものです:
-
\(u\) から \(v\) への路が存在しない場合、\(u\) から \(v\) への最短路も存在しない。この場合は \(\mathit{dist}(u, v) = \infty\) および \(\mathit{pred}(u, v) = \textsc{Null}\) とする。
-
\(u\) と \(v\) の間に負閉路がある場合、\(u\) から \(v\) の間には任意の負の長さを持つ路1が存在する。この場合は \(\mathit{dist}(u, v) = -\infty\) および \(\mathit{pred}(u, v) = \textsc{Null}\) とする。
-
\(u\) が負閉路上にない場合、\(u\) から \(u\) への最短路は辺を持たず、最後の辺が存在しない。この場合は \(\mathit{dist}(u, u) = 0\) および \(\mathit{pred}(u, u) = \textsc{Null}\) とする。
全組最短路問題の出力は二つの \(V \times V\) の配列であり、一つには\(V^{2}\) 個の最短路の距離2が、もう一つには \(V^{2}\) 個の前者が格納されます。ですがこの章では、距離の配列を計算することに集中します。最短路を実際に構築するために必要になる前者配列は、アルゴリズムをほんの少し改変するだけで計算できます (ヒント、ヒント)。