閉半環を使ってグラフ上の最短距離を計算する！

この記事は Haskell Advent Calendar 2020 21日目の記事です。 以前の記事でトロピカル行列を使ったグラフの最短経路の求め方を解説しました。 ここではトロピカルな隣接行列の累乗を収束するまで繰り返すという方法で最短経路を計算しましたが、実は閉半環という代数を考えると直接的に最短経路を求める計算が可能になります。そこで今回はその方法について解説したいと思います。 以前はHaskellのリスト [a] をベクトルとして行列を実装しましたが、今回はそれだと実装が少し煩雑になるので型レベル自然数を型引数に持つ Vector n a を中心に実装していきたいと思います。この話は以下の Functional Pearl が元になっていますが、この論文もリストを使って実装されているので Vector n a を使ってどのように実装できるかはこの記事で新しく試したところです。 ト