最短経路問題におけるアルゴリズム【ウォーシャル・フロイド法】の調査

佐藤　史隆, 廣安 知之, 三木 光範

ISDL Report　 No. 20040716001

2004年 4月 8日

Abstract

最短路・最短距離を求めるアルゴリズムであるウォーシャル・フロイド法（Warshall-Floyd法）について調査を行い, 報告した .

1  はじめに

本研究では, 効率の良いネットワークを遺伝的アルゴリズムにより作成することを目的としている. 最適化を行う際に, ネットワークの効率の良さを求めるために, ノード間の最短経路長を求める必要がある. 最短経路長を求めるアルゴリズムには, 全ての2点間の最短路・最短距離を求める方法であるウォーシャル・フロイド法（Warshall-Floyd法）, 特定の2点間の最短路・最短距離を求めるダイクストラ法（Dijkstra法）などがある. 本研究では, 全ての2点間の最短路・最短距離を求める必要があるため, ウォーシャル・フロイド法（Warshall-Floyd法）が有効であると考えられる. そこで, 本報告ではウォーシャル・フロイド法（Warshall-Floyd法）について調査を行い, 報告する.

2  ウォーシャル・フロイド法（Warshall-Floyd法）

全ての2点間の最短路・最短距離を求める方法にウォーシャル・フロイド法（Warshall-Floyd法）がある. まず, 点iからjに向かう枝がある場合はその距離dijを, ない場合は∞とした直接距離行列を作成する. 次に, iからjに別の1点を経由した場合（枝2本）の最短路・最短距離を求め, 距離行列を更新する. その際, 次に経由する点をpijとして記憶しておく. 更新された距離行列を用いてこの操作を再度行えば, 枝4本まで使った最短路・最短距離が求まる. この操作を2h≧n-1となるまでh回繰り返せば, 最終的な最短経路・最短距離が求まる.

2.1  アルゴリズム

前節で述べた手順をアルゴリズムとして以下に示す.

  1. pij=j(i∈N, j∈N), h=1とおく.
  2. 全てのi,j,k∈N(k≒i,j)に対し,

    dij＞dkjであれば, dij=dik+dkj, pij=pikとする.

  3. 2h≧-1であれば終了.
  4. h=h+1として2にもどる.

2.2  例

ウォーシャル・フロイド法（Warshall-Floyd法）を用いて, Fig.1 の問題を解いた場合の例を以下に示す.

Fig.1: 問題例

Table 1 , Table 2 , Table 3 , Table 4 , Table 5 , Table 6 に, step1～step3（h=1～3）についての処理を示す. なお, 各表の*は更新された箇所を示している.

Table 1: step1(h=1)におけるノード間の距離
dj 1 2 3 4 5
1 - 18 5 　 　
2 18 - 　 　 4
3 5 　 - 8 　
4 2 3 8 - 9
5 　 4 　 9 -

Table 2: step1(h=1)における経路
pij 1 2 3 4 5
1 - 2 3 4 5
2 1 - 3 4 5
3 1 2 - 4 5
4 1 2 3 - 5
5 1 2 3 4 -

Table 3: step2(h=2)におけるノード間の距離
dj 1 2 3 4 5
1 - 18 5 *13 *22
2 18 - *23 *13 4
3 5 *11 - 8 *17
4 2 3 *7 - *7
5 *11 4 *17 9 -

Table 4: step2(h=2)における経路
pij 1 2 3 4 5
1 - 2 3 *3 *2
2 1 - *1 *5 5
3 1 *4 - 4 *4
4 1 2 *1 - *2
5 *4 2 *4 4 -

Table 5: step3(h=3)におけるノード間の距離
dj 1 2 3 4 5
1 - *16 5 13 *20
2 *15 - *20 13 4
3 5 11 - 8 *15
4 2 3 7 - 7
5 11 4 *16 9 -

Table 6: step3(h=3)における経路
pij 1 2 3 4 5
1 - *3 3 3 *3
2 *5 - *5 5 5
3 1 4 - 4 *4
4 1 2 1 - 2
5 4 2 *4 4 -

ここでは次にどのノードを経由すればよいかをpij示し, 例えば②→③への最短経路は, ②→⑤→④→①→③と辿ればよいことが読みとれる.

3  まとめ

本報告では, ネットワークの全ての2点間の最短経路長を求めるアルゴリズムであるウォーシャル・フロイド法（Warshall-Floyd法）について, 調査し報告を行った.

References

[1]
Network on Network

http://homepage3.nifty.com/asagaya_avenue/net_theory.pdf

Copyright

Copyright (C) 2004 Tomoyuki Hiroyasu, All rights reserved.
Copyright (C) 2004 Mitsunori Miki, All rights reserved.
Copyright (C) 2004 Fumitaka Sato, All rights reserved.

No part of this document may be reproduced, copied, distributed,
transferred, modified, or transmitted, in any form or by any means,
without the prior written permission of the authors.
In no event shall the authors be liable for any damages caused in any way
out of the use of this document.



File translated from TEX by TTH, version 3.34.
On 14 May 2004, 13:19.
Back to Top