最小プラス行列乗算

最小プラス行列乗算は距離積とも呼ばれ、行列に対する演算です。

2 つの行列とが与えられたとき、それらの距離積はとなる行列として定義されます。これは、最小規則における 熱帯数の半環に対する標準的な行列乗算です。${\displaystyle n\times n}$${\displaystyle A=(a_{ij})}$${\displaystyle B=(b_{ij})}$${\displaystyle C=(c_{ij})=A\star B}$${\displaystyle n\times n}$${\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}}$

この操作は、最短経路問題と密接に関連しています。 がグラフの辺の重みを含む行列である場合、 は最大辺の長さの経路を使用して頂点間の距離を与え、はグラフの 距離行列です。${\displaystyle W}$${\displaystyle n\times n}$${\displaystyle W^{k}}$${\displaystyle k}$${\displaystyle W^{n}}$

• Uri Zwick . 2002. ブリッジング セットと長方形行列乗算を使用した全ペアの最短経路。J . ACM 49、3 (2002 年 5 月)、289–317。
• Liam Roditty と Asaf Shapira。2008。「サブ線形加法誤差を伴う全ペア最短経路」ICALP '08、パート I、LNCS 5125、pp. 622–633、2008。

• フロイド・ワーシャルアルゴリズム
• 熱帯の幾何学