フロイド／ウォーシャル法と豊穣圏論

スタンフォードのヴァーン・プラット（Vaughan Pratt）が1989年に書いた論文に

• ENRICHED CATEGORIES AND THE FLOYD-WARSHALL CONNECTION

というのがある。実質4ページ（1行はみ出して5ページ）だが、含蓄に富み面白い。「離散物理としてのグラフ理論 - 檜山正幸のキマイラ飼育記 メモ編」で参照している。

インターネットに残っているか？と思ったら、あった。よかった。

• http://boole.stanford.edu/pub/am4.pdf

冒頭に、次のアルゴリズムが出てくる。

for v do 

  for u, w do 

    δuw += δuv・δvw

アスキーだけで書けば：

for v in V {

  for u, w in V*V {

    d[u, w] += d[u, v]*d[v, w]

  }

}

d（もとのδ）は正方行列で、インデックス集合がV。単純有向グラフで言えば、頂点集合がVで、d[u, v]がuからvへの辺に付けられたラベル。ラベルのあいだに、+ と * という半環構造があれば、+= , * は意味を持つ。

上記の式は、頂点vを固定して、vの近傍であるスターごとに積和を取って、それをvに関して総和している。次のように書き換えると意味が変わる。

for u, w in V*V {

  for v in V {

    d[u, w] += d[u, v]*d[v, w]

  }

}

u, wを固定して、u, wを結ぶ短いパスに関して、すべてのパスに渡って総和し、それをすべての端点に関して足し上げる。

for文（総和、和分）の順序交換がある種の双対性になっている。