最短経路問題をマトリックスで解く

最短経路問題をマトリックスで解く at INFORMATICS

1:名無しさん＠お腹いっぱい。
22/09/10 15:52:11.21 uv+A97qg0.net
次のような4×４マトリックスA０があるとします。
a b c d
a 0 5 2 3
b 4 0 5 2
c 3 4 0 2
d 6 1 2 0
A0(c,b)＝4はcからbに行くには４時間かかるという意味です。
対角線が０なのは自分自身へは時間は不要という意味です。
ここでＡのc行（３，４，０，２）とAのb列（５，０，４，１）を足しますと（８，４，４，３）となります。
最小値は３で、その意味は「cからbへは一か所経由すれば3時間で行ける」となります。
最小値３は4番目にありますからdを通過すればよいことがわかります。
この操作にはc～c～bやc～b～bも含まれますので、「一か所経由」は正確には「最大でも一か所経由」です。
A0のあらゆる行と列の組み合わせに対してこの演算をやりますと新たなマトリックスA1ができ、対応する経由地のマトリックスQ1も得られます。
次にA1に対してA0に行った操作をしてA2を得ます。
A2は最大3か所立ち寄った場合の最短時間となります。
この例の場合ノード数は4しかありませんのですべてのノード間の最短時間が得られました。
経由地マトリックスQ2も得られます。
i～ｊの最短時間はA2(i,j)にあります。
i～ｊの最短経路はまずi～Ｑ２(i,j)～jが得られます。
i～Ｑ２(i,j)にＱ１を適用し、Ｑ２(i,j)～jにＱ１を適用すれば、具体的な最短経路が得られます。
添付： URLﾘﾝｸ(sites.google.com)

レスを読む