フロイド／ウォーシャル法とダイクストラのアルゴリズム

ちょっと考えてわかったこと： フロイド／ウォーシャル法は半環係数で考えても非常に一般的な方法だ。境界付きグラフ（リグラフ）の始境界であたえられた初期値が無限の未来に終境界にどのような影響を与えるかを計算する。

ダイクストラのアルゴリズムは、始境界も終境界も1点である場合のフロイド／ウォーシャル法と同等である。例えば、点光源から出た球面波の別な一点への影響とか。積分（総和）する量（重さ、コスト、長さなど）が比較可能なとき、重ね合わせの代わりに比較を用いると、変分原理との関係が出てくる。

離散的な場合の比較は、マックス・プラス代数またはミニ・プラス代数を用いた定式化となり、変分原理の局所版としてベルマンの原理が使える。ベルマン方程式は、次の形に書ける。ここで、aは基点、N₊(x) は、点xに入る隣接点の集合、Lは基点からの大域的最適値（距離など）、a(y, x)はyからxに至る辺に与えられたコスト。

• L(a) = 0
• L(x) = min{y∈N₊(x) | L(y) + a(y, x)}

記法を変えて、和を積、minを和の形にして、A(y, x)を辺に割り当てられた接続係数だとすると、

• L(a) = e
• L(x) = Σ{y∈N₊(x) | A(y, x)・L(y)}

のように書けるが、これは点xでの値を基点aからの経路和（経路積の重ね合わせ）で求める公式に他ならない。