2022年　9月   山本正弘　

1981年に物流倉庫の場所を決める必要があり、全ノード間の最短経路（全点対最短経路）  をマトリックス演算で算出した。この時はIBMのAPL言語を用いたが、他の言語でも可能である。以下（１）で例を使って説明する。

APL言語の特徴を一つだけ説明すると、マトリックスA、Bの積はA＋. ×Bで表す。右から左へ演算し、＋. ×は内積を表している。＋と×をそれぞれAPL記号の⌊（最小値演算子）と＋に置き換えれば、A⌊.＋Bは、現在で言うところのトロピカルなマトリックス積となる。C←A⌊.＋Bを数学的に書けば、A、B、CをN×Nマトリックスとして、C(i,j)=min{A(i,k)＋B(k,j)}k=1,....,Nである（min-sum product、min-plus matrix multiplicationといわれる）。Aを経路の隣接マトリックスとする時、min-sum product　A←A⌊.＋Aをlog2N回繰り返せば全点対の最短時間がえられる。計算量はN×N×N×log2Nである。

min-sum productを◎、隣接マトリックスをA、最短時間マトリックスをWとすると、W◎A＝Wの関係があり、この等式から、Wを求める事も出来る。この解法を以下（３）で例示する。

（１）アルゴリズムの説明

ノード間の交通時間をマトリックスで表す。Ａ0は下図の隣接マトリックスである。例えば、aとbは隣接しており、2単位時間かかり、Ａ0(a，b)=Ａ0(1，2)=2、Ａ0(b，a)=Ａ0(2，1)=2である。自分自身へ行く時間は０である（対角線は０）。∞は隣接していないことを示している。

Ａ1=Ａ0◎Ａ0を作る。Ａ1(ⅰ,j)=min{Ａ0(i,k)＋Ａ0(k,j)}k。Ａ0(i,k)＋Ａ0(k,j)は経路i→k→jの時間である。Ａ1(ⅰ,j)はkをすべてのノードに亘って動かした場合の最小値であるから、iからjに行くのに一か所経由した場合の最小値を表している。どこにも立ち寄らない場合、すなわちＡ0(i,i)＋Ａ0(i,j)とＡ0(i,j)＋Ａ0(j,j)も含んでいるので最大一か所経由になる。

経由地マトリックスQ1を作る。Q1(ⅰ,j)＝{Ａ0(i,k)＋Ａ0(k,j)}kが最小値の時のk。最小値が複数あるときは、たとえば最初のkとする。

例、Ａ1(2,4）を求める。Ａ0の2行目｛2，0，5，∞，１，∞，∞，∞，∞｝とＡ0の4列目｛7，∞，∞，0，2，∞，3，∞，∞｝の和を取ると、｛9，∞，∞，∞，3，∞，∞，∞，∞｝。最小値は3であるからＡ1(2,4)=3。最小値は5番目にあるから5=eでQ1(2,4)＝eとなる。

Ａ2=Ａ1◎ Ａ1はＡ1を隣接マトリックスと見た場合、最大一か所立ち寄った時に得られる最小時間である。Ａ2=Ａ1◎ Ａ1=Ａ0◎ Ａ0◎ Ａ0◎ Ａ0であるから立ち寄り先は最大３か所である。経由地マトリックスQ2はQ1と同様、Ａ2算出時の最小値の時の立ち寄り先である。

Ａ3＝Ａ2◎ Ａ2はＡ2を隣接マトリックスとした場合の最大一か所立ち寄った時に得られる最小時間である。Ａ0をベースにすれば、Ａ3＝Ａ2◎ Ａ2＝Ａ0◎ Ａ0◎ Ａ0◎ Ａ0◎Ａ0◎ Ａ0◎ Ａ0◎ Ａ0であるから最大７か所立ち寄った場合となる。

この例では、目視で最大５か所立ち寄る最短経路があり、それ以上はないので、Ａ4＝Ａ3であり計算を略した。ノード数をNとするとlog2N回の演算を行えば、最短時間、最短経路が算出できるので、このアルゴリズムの計算量は、N×N×N×log2Nである。

（２）最短経路の求め方。

インデックスをノードに置き換える。1=a,2=b,3=c,4=d,5=e,6=f,7=g,8=h,9=i。

aからiに行く最短時間はＡ3により11である。Q3によりdを経由しており、経路はa→d→i。つぎにQ2によりa→dはa→b→d、d→iはd→g→iに展開される。続いてQ1によりb→dはb→e→d、g→iはg→h→iに展開され、a→b→e→d→g→h→iが最短経路である。

（３）最短時間マトリックスの別解（2024年10月追加）

Aを隣接マトリックスとすると、最短時間マトリックスWはW◎A＝Wなる性質を持つ。A の要素は負値はとらないとすると式W◎A＝WからつぎのようにWを求める事ができる。

Wのある行を（X1, X2,,,,, XN）とする。Xi（i=1,2,,,,N）≧０。（X1, X2,,,,, XN）◎A＝(X1, X2,,,,, XN）が成り立つ。（X1, X2,,,,, XN）がi行目であればXi=0。以下のように変数を順に消去してゆけば、（X1, X2,,,,, XN）が得られる。例えば隣接マトリックを上記例題のA0として、Wの4行目を求めてみる。（X1, X2,,,,, X9）◎A0＝(X1, X2,,,,, X9）から以下を得る。

X1=min{ X1,X2+2, X3+∞,X4+7, X5+∞, X6+∞, X7+∞, X8+∞, X9+∞}

X2=min{ X1+2, X2,X3+5, X4+∞, X5+1, X6+∞, X7+∞, X8+∞, X9+∞}

X3=min{ X1+∞, X2+5, X3, X4+∞, X5+∞, X6+4, X7+∞, X8+∞, X9+∞}

X4＝０

X5=min{ X1+∞, X2+1 X3+∞, X4+2, X5, X6+6, X7+∞, X8+8, X9+∞}

X6=min{ X1+∞, X2+∞, X3+4, X4+∞, X5+6, X6, X7+∞, X8+∞, X9+10}

X7=min{ X1+∞, X2+∞, X3+∞, X4+3, X5+∞, X6+∞, X7 ,X8+2, X9+∞}

X8=min{ X1+∞, X2+∞, X3+∞, X4+∞, X5+8, X6+∞, X7+2, X8 , X9+1}

X9=min{ X1+∞, X2+∞, X3+∞, X4+∞, X5+∞, X6+10, X7+∞, X8+1 X9}

これらから、Xi=min{…, Xi, …}中の意味のないXiを除去する。

X4=0を代入する。∞の項目はmin演算に影響を与えないので除去すると以下のようになる。

X1=min{ X2+2, 7 }……（1）

X2=min{ X1+2, X3+5, X5+1}………(2)

X3=min{ X2+5, X6+4}………(3)

X5=min{ X2+1, 2, X6+6,X8+8}からX5=min{ X2+1, 2}………(4)

X6=min{ X3+4, X5+6, X9+10}………(5)

X7=min{ 3, X8+2 }………(6)

X8=min{ X5+8, X7+2, X9+1}………(7)

X9=min{ X6+10, X8+1}………(8)

(4)を（2）に代入すると、X2=min{ X1+2, X3+5, X2+1+1, 2+1}。整理すると、X2=min{ X1+2, X3+5, 3}。

これを（1）に代入整理するとX1=min{ X1+4, X3+7, 5, 7 }からX1=min{ X3+7, 5}からX1=5。X2=3。（4）からX5=2。

(3)に(5)を代入整理してX3=min{8, X3+8, 12, X9+14}からX3=8。

 X6=min{ 8+4, 2+6, X9+10}からX6=8。

(7)に(6)を代入してX8=min{10,5, X8+4, X9+1}から、X8=min{5, X9+1}。

(8)に(5)を代入して、X9=min{X3+4+10, X5+6+10, X9+10+10, X8+1}。

これをX8=min{5, X9+1}に代入してX8=5。これから X9=6。 X7=3。

（X1, X2,,,,, X9）＝（5,3,8,0,2,8,3,5,6）が得られ、前記A3の4行目に一致する。