練習問題

1. $\textsc{LeyzorekAPSP}$ を改変して、最短路の長さの配列だけはなく前者へのポインタの配列も計算するようにしてください。実行時間は $O(V^{3}\log V)$ のままであるようにしてください。
2. $\textsc{FloydWarshall}$ を改変して、最短路の長さの配列だけはなく前者へのポインタの配列も計算するようにしてください。実行時間は $O(V^{3})$ のままであるようにしてください。
この章で議論した全てのアルゴリズムは負閉路が含まれるグラフに対して正しい答えを計算できません。グラフに負閉路が含まれている場合、Johnson のアルゴリズムでは最初の Bellman-Ford が負閉路を検出して実行がそこで終了し、動的計画法のアルゴリズムでは間違った答えが計算されます。

しかしこの章で議論した全てのアルゴリズムは、負閉路が含まれている場合でも最短路の長さを正しく計算するようにできます。つまり:
- $u$ が $v$ に到達できないなら、$\mathit{dist}[u, v] = \infty$ を返す。
- $u$ が $v$ に到達できる負閉路に到達できるなら、$\mathit{dist}[u, v] = -\infty$ を返す。
- それ以外の場合、$u$ から $v$ への最短路が存在するので、その長さを返す。
となるようにアルゴリズムを改変できるということです。
1. $\textsc{JohnsonAPSP}$ を改変して、負閉路が含まれている場合でも最短路の長さを正しく計算できるようにしてください。
2. $\textsc{LeyzorekAPSP}$ を改変して、負閉路が含まれている場合でも最短路の長さを正しく計算できるようにしてください。
3. $\textsc{FloydWarshall}$ を改変して、負閉路が含まれている場合でも最短路の長さを正しく計算できるようにしてください。
この章で議論した全てのアルゴリズムは、入力グラフ $G$ に負閉路が含まれているかどうかを報告するだけではなく、$G$ に含まれる負閉路を検出したときにその負閉路を返すように改変できます。
1. $\textsc{JohnsonAPSP}$ を改変して、要素が最短路の長さの配列または負閉路を返すようにしてください。
2. $\textsc{LeyzorekAPSP}$ を改変して、要素が最短路の長さの配列または負閉路を返すようにしてください。
3. $\textsc{FloydWarshall}$ を改変して、要素が最短路の長さの配列または負閉路を返すようにしてください。
全ての場合において、入力グラフに複数の負閉路が含まれる場合にはどれを選んでも構いません。
$G = (V, E)$ を辺に重みの付いた有向グラフとし、辺の重みは任意の実数で、負閉路は含まれないとします。
1. 重みがゼロである閉路を見つけるか、そのような閉路が無ければそうだと正しく報告する効率の良いアルゴリズムを説明してください。
2. 次の条件を満たす $G$ の部分グラフ $H$ を構築する効率の良いアルゴリズムを説明してください。
  - $H$ は $G$ の全ての頂点を含む。
  - $H$ の全ての閉路は重みがゼロである。
  - $G$ に含まれる重みがゼロの閉路は全て $H$ に含まれる。
  例えば $G$ がゼロ閉路を持たない場合、$H$ は辺を持ちません。
$G = (V, E)$ を辺に重みの付いた有向グラフとし、辺の重みは任意の実数とします。$G$ の頂点を $k$ 個の互いに素な部分集合 $V_{1}, V_{2}, \ldots, V_{k}$ に分割したとします。つまり、$G$ の全ての頂点がちょうど一つの部分集合 $V_{i}$ に属するということです。任意の添え字の組 $i, j$ について、$\delta(i, j)$ で $V_{i}$ に属する頂点から $V_{j}$ に属する頂点への最短路の長さの最小値を表すことにします: \[ \delta(i, j) = \min \lbrace \mathit{dist}(v_{i}, v_{j})\ |\ v_{i} \in V_{i} \text{ かつ } v_{j} \in V_{j} \rbrace \] 全ての $i, j$ について $\delta(i, j)$ を計算するアルゴリズムを説明してください。満点のためには実行時間が $O(VE + kV\log V)$ であることが求められます。
この問題はあなたが、そうですあなたが、ウォールストリートで職を得て大規模な経済崩壊を起こすことができるかどうかを試します！アービトラージビジネスとは、為替交換の鞘を利用して儲ける手法を言います。例えば 1 US ドルが 120 円で、1 円が 0.01 ユーロで、1 ユーロが 1.2 US ドルのとき、1 ドルを持っているトレーダーはそのドルを円に、円をユーロに、ユーロをドルに交換することで 1.44 ドルを入手できます！この例における $ → ¥ → € → $ のような通貨のサイクルのことをアービトラージサイクル (arbitrage cycle) と言います。もちろん、アービトラージサイクルを見つけて儲けるには極限まで高速なアルゴリズムが必要です。

$n$ 個の異なる通貨が取引される為替市場で、その交換レートが行列 $R[1..n, 1..n]$ で与えられるとします。任意の添え字 $i, j$ について一単位の通貨 $i$ が $R[i, j]$ 単位の通貨 $j$ と交換可能なことを表すとします ($R[i, j] \cdot R[j, i] = 1$ が成り立つとは限りません)。
1. アービトラージサイクルが存在しないと仮定します。一単位の通貨 $1$ から交換をしていったときに最大で入手できる通貨 $i$ の金額が $V[i]$ であるような配列 $V[1..n]$ を計算するアルゴリズムを説明してください。
2. 与えられた為替交換レートを表す行列にアービトラージサイクルが含まれるかどうかを判定するアルゴリズムを説明してください。
3. (b) のアルゴリズムを改変してアービトラージサイクルが存在する場合にはそれを返すようにしてください。
Morty はクラックスパイア迷宮 (Clackspire Labyrinth) から安定化したプランバス (plumbus) を取ってこようとしています。Morty は Rick の異次元ポータル銃を使って迷宮に入り、迷宮をプランバスの所まで進み、さらにフリーブ (fleeb) の所まで進んでプランバスを安定化させ、そして入ってきたポータルに戻って来ます。プランバスはフリーブのジュースで安定化させることができ、このジュースはフリーブを巣穴から動かすとすぐに放出されます。また安定化されていないプランバスを保管場所から 137 flink 以上遠くに動かすと爆発します。クラックスパイア迷宮はおならのようなにおいが充満しているので、Morty はなるべく短い時間で仕事を終わらせようと思っています。

Morty は Rick からクラックスパイア迷宮の詳細な地図をもらいました。この地図は辺に非負の重みが付いた有向グラフ $G = (V, E)$ であり、重みが距離 (単位は flink) を表します。また $P \subset V$ と $F \subset V$ も与えられ、$P$ がプランバスの保管場所を、$F$ がフリーブの巣穴を表します。Morty は探索を始める頂点 $s \in V$ と使用するプランバスの保管場所 $p \in P$ とフリーブの巣穴 $f \in F$ を決めるのですが、そのとき $p$ から $f$ への最短路の長さは 137 flink 以下で、かつ $s \rightsquigarrow p \rightsquigarrow f \rightsquigarrow s$ の長さは最短である必要があります。

Morty の問題を (ゲフッ) 解くアルゴリズ (グフッ) ムを説明、解析してください。Morty がこの仕事を行えると仮定して構いません。
辺に重みの付いた有向グラフを $G = (V, E)$ とし、辺の重みは任意の実数とします。
1. どの頂点の組の間の最短路の長さも変化しないようにいずれかの頂点 $v$ を取り除くことができるでしょうか？部分グラフ $G^{\prime} = (V \backslash \lbrace v \rbrace, E)$ であって $G^{\prime}$ に含まれる任意の頂点の組の間の最短路の長さが $G$ における同じ頂点の間の最短路の長さと同じであるものを $O(V^{2})$ 時間で構築するアルゴリズムを説明してください。
2. $G^{\prime}$ における全ての頂点の組に対する最短路の距離が既に求まっているとします。$v$ から他の全ての頂点への最短路の長さと他の全ての頂点から $v$ への最短路の長さを $O(V^{2})$ 時間で計算するアルゴリズムを説明してください。
3. (a) と (b) を組み合わせて、 $O(V^{3})$ 時間で動作する本文中で説明したのと異なる全組最短路アルゴリズムを説明してください (答えのアルゴリズムは Floyd-Warshall とほとんど同じです)。
次の三種類目の行列積もまた最短路アルゴリズムに関係があります。$n \times n$ 行列 $A, B$ の "boolean 積" あるいは"and-or 積" $C$ は次のように定義されます: \[ C[i,j] := \bigvee_{k} \left(A[i, k] \land B[k,j] \right) \]
1. boolean 行列積を min-plus 行列積に帰着させてください。つまり、二つの $n \times n$ 行列の min-plus 積を $T(n)$ 時間で計算するサブルーチン $\textsc{MinPlusMaltiply}$ が与えられたときに、このサブルーチンを使って二つの $n \times n$ 行列の boolean 積を $O(T(n))$ 時間で計算するアルゴリズムを説明、解析してください。
2. boolean 行列積を通常の行列積に帰着させてください。つまり、二つの $n \times n$ 行列の通常の積を $T(n)$ 時間で計算するサブルーチン $\textsc{MatrixMaltiply}$ が与えられたときに、このサブルーチンを使って二つの $n \times n$ 行列の通常の積を $O(T(n))$ 時間で計算するアルゴリズムを説明、解析してください。
有向グラフ $G$ の推移閉包 (transitive closure) とは $G$ と同じ頂点を持つグラフであって、$u \rightarrow v$ という辺が存在するのが $G$ において $u$ から $v$ に路が存在するときに限るものを言います。
1. ある $2 \leq \omega < 3$ に対して、二つの $n \times n$ 行列の boolean 行列積が $O(n^{\omega})$ 時間で行えるとします (練習問題 9.9.(b) から $\omega \leq 2.372864$ が分かります)。$n$ 頂点の有向グラフの推移閉包を $O(n^{\omega} \log n)$ 時間で計算するアルゴリズムを説明してください。
2. $G$ を有向非巡回グラフとします。$G$ の推移閉包を $O(V^{\omega})$ 時間で計算するアルゴリズムを説明してください。 [ヒント: DAG に必ず行うあの処理をして、さらに分割統治をします。$\omega \geq 2$ を使います。]
3. $G$ を任意の巡回グラフとします。$G$ の推移閉包を $O(V^{\omega})$ 時間で計算するアルゴリズムを説明してください。 [ヒント: 任意の有向グラフを DAG にするときに必ず行うあの処理をします。]
4. 前問の逆を行いましょう。ある $2 \leq \alpha < 3$ について、$n$ 頂点の有向グラフを受け取って $O(n^{\alpha})$ 時間で推移閉包を計算するサブルーチン $\textsc{TransitiveClosure}$ が与えられたときに、$n \times n$ の boolean 行列積を $O(n^{\alpha})$ 時間で計算するアルゴリズムを説明、解析してください。
次に示す再帰的なアルゴリズムが全組最短路の距離を $O(n^{3})$ 時間で正しく計算することを示してください。問題を単純にするために、$n$ が $2$ のべきであると仮定してください。これまでと同じように、ヘルパー関数 $\textsc{RecAPSP}$ に渡される配列 $D$ は参照で渡されます。 [ヒント: このアルゴリズムは一目見ただけでは Floyd-Warshall を分かりにくくしたものに過ぎませんが、キャッシュの振る舞いがはるかに優れています¹。]

procedure $\texttt{RecursiveAPSP}$($V, E, w$)

$n \leftarrow |V|$

for $i \leftarrow 1$ to $n$ do

for $j \leftarrow 1$ to $n$ do

if $i = j$ then

$D[i, j] \leftarrow 0$

if $i \rightarrow j \in E$ then

$D[i, j] \leftarrow w(i \rightarrow j)$

else

$D[i,j] \leftarrow \infty$

$\texttt{RecAPSP}$($D, n, 1, 1, 1$)

return $D[1..n, 1..n]$

procedure $\texttt{RecAPSP}$($D,n,i,j,k$)

if $n=1$ then

$D[i,j] \leftarrow \min \lbrace D[i,j],\ D[i,k] + D[j,k] \rbrace$

else

$m \leftarrow n / 2$

$\texttt{RecAPSP}$($D,\ n/2,\ i,\ \hphantom{,+m} j,\ \hphantom{,+m} k \hphantom{,+m} $)

$\texttt{RecAPSP}$($D,\ n/2,\ i,\ \hphantom{,+m} j,\ \hphantom{,+m} k+m $)

$\texttt{RecAPSP}$($D,\ n/2,\ i,\ \hphantom{,+m} j+m,\ k \hphantom{,+m} $)

$\texttt{RecAPSP}$($D,\ n/2,\ i,\ \hphantom{,+m} j+m,\ k+m $)

$\texttt{RecAPSP}$($D,\ n/2,\ i+m,\ j,\ \hphantom{,+m} k \hphantom{,+m} $)

$\texttt{RecAPSP}$($D,\ n/2,\ i+m,\ j,\ \hphantom{,+m} k+m $)

$\texttt{RecAPSP}$($D,\ n/2,\ i+m,\ j+m,\ k \hphantom{,+m} $)

$\texttt{RecAPSP}$($D,\ n/2,\ i+m,\ j+m,\ k+m $)
❤ $n$ 頂点の重み無し連結無向グラフを $G = (V, E)$ とし、$G$ の隣接行列を $A[1..n, 1..n]$ とします。この問題では最短路の長さを収めた行列 $D[1..n, 1..n]$ を計算する、Seidel によって示されたアルゴリズムを考えます。このアルゴリズムは高速な行列乗算を使っており、$O(n^{3})$ よりも高速です。

ある定数 $\omega \geq 2$ に対して、二つの $n \times n$ 行列の積を $O(n^{\omega})$ 時間で計算するサブルーチン $\textsc{MatrixMaltiply}$ が使えるとします。
1. $G$ と同じ頂点を持ち、頂点の組の間に辺があるのが $G$ においてそれらの間に長さが 2 以下の路があるときに限られるようなグラフを $G^{2}$ とします。一度の $\textsc{MatrixMaltiply}$ 呼び出しと $O(n^{2})$ 時間の追加の計算を使って $G^{2}$ の隣接行列を計算するアルゴリズムを計算してください。
2. $G^{2}$ が完全グラフだとします。$G$ の最短路を収めた行列 $D$ を $O(n^{2})$ 時間の追加の計算で計算するアルゴリズムを説明してください。
3. $G^{2}$ の最短路の距離を収めた行列 $D^{2}$ を再帰的に計算するとします。$G$ における $i$ から $j$ への最短路の長さが $2 \cdot D^{2}[i, j]$ または $2 \cdot D^{2}[i, j] - 1$ であることを示してください。
4. $G^{2}$ が完全グラフでないとします。$X = D^{2} \cdot A$ とし、$\deg (i)$ で $G$ における頂点 $i$ の次数を表すことにします。頂点 $i$ から頂点 $j$ への最短路の長さが $2 \cdot D^{2}[i, j]$ となるのは $X[i, j] > D^{2}[i,j] \cdot \deg(i)$ である場合に限ることを証明してください。
5. $G$ の最短路の長さを収めた行列 $D$ を $O(n^{\omega} \log n)$ 時間で計算するアルゴリズムを説明してください。
Gideon Yuval は 1976 年、次に示す min-plus 行列乗算から通常の行列乗算への帰着を提案しました。$A, B$ を $n \times n$ の行列とし、要素は $0$ から $M$ の整数だとします。このとき $A$ と $B$ の min-sum 積 \[ C[i,k] = \min\limits_{j}(A[i,j] + B[j,k]) \] を全ての $i, j$ について計算します。新しい $n \times n$ 行列 $A^{\prime}, B^{\prime}$ を \[ \begin{aligned} A^{\prime}[i,j] & = n^{M-A[i,j]} \\ B^{\prime}[i,j] & = n^{M-B[i,j]} \end{aligned} \] と定義し、$A^{\prime}$ と $B^{\prime}$ の (通常の) 積を $C^{\prime}[i,k] = \sum_{j} A^{\prime}[i, j] \cdot B^{\prime}[j, k]$ とします。
1. 通常の整数演算 ($+, -, \times$) だけを使って $A$ から $A^{\prime}$ を計算するアルゴリズムを説明してください。
2. 通常の整数演算 ($+, -, \times$) だけを使って $C^{\prime}$ から min-sum 積 $C^{\prime}$ を計算するアルゴリズムを説明してください²。
3. ある $2 \leq \omega < 3$ について、$n \times n$ 整数行列の (通常の) 積を $O(n^{\omega})$ 回の算術演算で計算できるとします。Yuval のアルゴリズムを使って min-sum 積 $C$ を計算するのに算術演算は何回必要になりますか？
4. $n \times n$ の整数行列 $A$ が与えられたときに、$A$ の $n$ "おかしな"乗を Yuval のアルゴリズムを使って求めるのに算術演算は何回必要になりますか？ ($A$ が重み付き隣接行列とすれば、その $n$ "おかしな" 乗は最短路の長さを収めた行列であることを思い出してください)
5. 任意の重みを持つグラフを考えたときには、Yuval のアルゴリズムが Floyd-Warshall のアルゴリズムよりも速い全組最短路アルゴリズムとはなりません。どうしてですか？ごまかしが起こっているのはどこですか？

Joon-Sang Park, Michael Penner, and Viktor K. Prasanna. Optimizing graph algorithms for improved cache performance. IEEE Trans. Parallel and Distributed Systems 15(9):769–782, 2004. さらに広い動的計画法アルゴリズムのクラスの大幅な一般化については次の文献を参照してください: Rezaul Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. Proc. 17th SODA 591–600, 2006^[return]
対数や割り算、それから床関数 $\lfloor x \rfloor$ を使わないでください。信じてください ――これは開けてはいけないドアです。^[return]