ワーシャルフロイド法（Warshall-Floyd Algorithm）とは
ワーシャルフロイド法とは、
です。
最小経路とはスタートからゴールまでに通るパスの和が最小になるもののことです。
以下の例では、AからBまでの最短経路はA→D→Bとなります。
ワーシャルフロイド法では負の重みを持つ辺が含まれていても適用可能です。
ただし、負閉路（負の重みの総和が負になる閉路）が存在する場合は、正しく最短経路を求めることができません。
最短経路を求める方法は他にも、ダイクストラ法やベルマンフォード法などがあります。
アルゴリズムの概要
1. 隣接行列を初期化
グラフを隣接行列の形で表し、既知の距離を設定します。
例えば、dist[A][B] は「A から B への最短距離」を示し、A -> B の距離は 3、A -> C の距離は 2 です。
直接つながっていない経路は無限大を設定します。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | ∞ | 3 | |
| C | 5 | ∞ | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
2. 経由地点を設定して更新
各頂点を順番に経由地点として、そこを通る経路が近道であるかを確認して距離を更新します。
Aを経由地点とする
Aからスタートするパターンは変化がないため割愛します。
Bからスタートするパターンは、B→A→CとB→A→Dについて見ていきます。
（B→AとB→A→Bについては割愛します。）
B→A→Cの距離はB→A（20）とA→C（5）の和になります。
B→C（∞）と比べて小さくなるので、隣接行列を更新します。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | 25 | 3 | |
| C | 5 | ∞ | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
続いてB→A→Dです。
B→A→Dの距離はB→A（20）とA→D（10）の和になります。
B→D（3）と比べて大きいので、隣接行列に変更はありません。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | 25 | 3 | |
| C | 5 | ∞ | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
これを全ての頂点の組み合わせで行います。
今回の場合は、C→A→B、C→A→D、D→A→B、D→A→Cを確認します。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | 25 | 3 | |
| C | 5 | 25 | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
Bを経由地点とする
続いてBを経由地点として、全ての経路の距離を確認していきます。
A→B→C、A→B→D、C→B→A、C→B→D、D→B→A、D→B→Cの経路を見ていきます。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | 25 | 3 | |
| C | 5 | 25 | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
Cを経由地点とする
上記と同様にCを経由地点として、全ての経路の距離を確認していきます。
A→C→B、A→C→D、B→C→A、B→C→D、D→C→A、D→C→Bの経路を見ていきます。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 20 | 5 | 10 |
| B | 20 | 0 | 25 | 3 | |
| C | 5 | 25 | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
Dを経由地点とする
最後にDを経由地点として、全ての経路の距離を確認していきます。
A→D→B、A→D→C、B→D→A、B→D→C、C→D→A、C→D→Bの経路を見ていきます。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 13 | 5 | 10 |
| B | 13 | 0 | 13 | 3 | |
| C | 5 | 13 | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
3. 最短経路の決定
すべての経由点の考慮が終わった時点で、各頂点間の最短経路が確定します。
| |
ゴール |
||||
| A | B | C | D | ||
| スタート | A | 0 | 13 | 5 | 10 |
| B | 13 | 0 | 13 | 3 | |
| C | 5 | 13 | 0 | 10 | |
| D | 10 | 3 | 10 | 0 | |
負の閉路を検出するには、アルゴリズムの最後に対角成分（dist[i][i]）が負であるかを確認することで判別できます。
実装(Python)
ワーシャルフロイド法をpythonで実装した例です。
INF = float('inf')
def floyd_warshall(graph):
num_vertices = len(graph)
dist = [row[:] for row in graph] # グラフのコピー
for via in range(num_vertices):
for start in range(num_vertices):
for end in range(num_vertices):
via_dist = dist[start][via] + dist[via][end]
if via_dist < dist[start][end]:
dist[start][end] = via_dist
# 負の閉路の検出
for i in range(num_vertices):
if dist[i][i] < 0:
print("負の閉路が存在します。")
return None
return dist実行してみます。
# 隣接行列の例
adj_matrix = [
[0, 20, 5, 10],
[20, 0, INF, 3],
[5, INF, 0, 10],
[10, 3, 10, 0]
]
result = floyd_warshall(adj_matrix)
if result:
for row in result:
print(row)[0, 13, 5, 10]
[13, 0, 13, 3]
[5, 13, 0, 10]
[10, 3, 10, 0]
参考文献
コメント