フロイド／ウォーシャル法と行列計算

もともとの（かなり狭義の）フロイド／ウォーシャル法では、無向グラフ上の最短距離行列や最短経路を求める。

有向グラフにして、距離を非負値コストにしてもたいして事情はかわらない。[0, ∞] に min-plusをいれた加法的ベキ等半環を係数域とする行列計算になる。

Aのクリーネスター級数の打ち切り多項式を A^[n] と書くことにする。A^* = A^[∞] 。フロイド／ウォーシャルのアルゴリズムとしてのキモは、累乗の計算を 2, 4, 8, 16 と2のベキで行うので速いことだろう。2のベキで済む根拠は次のこと。

1. Aⁿ⁺¹ = Aⁿ となるようなnがあるとき、Aはベキ安定とでも呼ぶ（なんか用語があるのか？）。グラフの直達距離行列（あるいはコスト行列）Aはベキ安定である。
2. 加法的ベキ等半環を係数とする行列では、A^[n]×A^[n] = A^[2n] という公式が成立する。

最短経路（または最小コスト経路）に関しては、長さが (頂点数 - 1) で抑えられることから、ベキ安定が出てくる。min-plusの性質から、A = A^[1] = I + A となり、A×A = A^[1]×A^[1] = A^[2] が成立。A^[2]×A^[2] = A^[4] 、… を繰り返すと割とすぐに安定する。

実際の経路はどうでもよくて、最短距離行列が欲しいなら、2点を固定して、中継点を動かして検索した最小値ともとの値の比較を繰り返す。計算が楽なわけじゃないが、もともとがたくさんの組み合わせを試す問題だからな。

いい忘れたが、推移的閉包ってクリーネスター。文法で生成される言語もクリーネスター。離散半方向時間の半S行列（片側S行列）もクリーネスター。行列Aのnステップ後の波頭がAⁿで、掃過域がA^[n]。無限時間後だと波頭は意味がないが、履歴を全部累積した掃過域は意味を持つ。初期状態から、効果を無限に累積した後の姿がクリーネスターってことだな。これを作用素と考えると、現在から無限の未来（安定状態）を計算する作用。