ワーシャル・フロイド法は、グラフ理論における全点対間最短経路問題を解くためのアルゴリズムです。動的計画法を応用し、効率的にすべての頂点間の最短経路を計算します。
[PR] 数理最適化について気軽に学べるUdemyコース
全点対間最短経路問題とワーシャル・フロイド法
グラフ内の任意の2頂点間の最短経路（最もコストの低い経路）を求める問題です。 例えば、旅行の計画を立てる際、行きたい複数の都市があり、それぞれの間の移動手段と所要時間（または費用）が異なるとします。そのような場合、どの都市からどの都市へ行くにも、最も効率的なルート（最短時間または最小費用）を知りたいと思います。このような問題を解くことができるのがワーシャル・フロイド法です。
ワーシャル・フロイド法
ワーシャル・フロイド法は、1960年代にそれぞれ独立に発表されたアルゴリズムです。Robert Floyd（ロバート・フロイド）は、既に知られていたStephen Warshall（ステファン・ワーシャル）のアルゴリズム（推移的閉包を求めるアルゴリズム）を元に、最短経路問題を解くアルゴリズムを考案しました。当時、コンピュータの性能は非常に限られていましたが、ワーシャル・フロイド法はそのシンプルさから、効率的に全点対間最短経路を計算できる強力な手法として広く受け入れられました。
ワーシャル・フロイド法の概要
ワーシャル・フロイド法は、全頂点間の最短経路を一度に計算するアルゴリズムです。動的計画法の考え方に基づき、段階的に最短経路情報を更新していくことで、最終的に全頂点間の最短経路を求めます。
ワーシャル・フロイド法特徴
全点対間最短経路を一度に計算します。負のコストを持つ辺が存在しても動作します （ただし、負の閉路が存在する場合は検出できます）。シンプルな考え方で、実装が比較的簡単です。
ワーシャル・フロイド法の原理
1. 初期化
各頂点間の距離を、直接接続されている場合はその辺のコスト、そうでない場合は無限大 (INF) で初期化します。これは、現時点で判明している最短経路情報とみなせます。
2. 更新 (動的計画法による段階的更新)
ここがワーシャル・フロイド法の最も重要な部分です。経由する頂点を1つずつ増やしながら、全頂点間の最短距離を更新していきます。
経由頂点
kの導入- まず、頂点1だけを経由してよい、という条件下で全頂点間の最短経路を求めます。次に、頂点1と頂点2を経由してよい、という条件下で…というように、経由してよい頂点を増やしていきます。
最短距離の更新ルール
- 頂点
kを経由するとして、頂点iから頂点jへの最短距離を考えます。この時、以下の2つの経路のコストを比較しますiからjへの既存の最短距離 (現時点での最短距離)iからkへの最短距離 +kからjへの最短距離 (頂点kを経由した場合の距離)
- 頂点
そして、これらのうち、より小さい方を新しい i から j への最短距離として採用します。
なぜこの更新でうまくいくのか
最初は、どの頂点も経由しない場合の最短経路（つまり直接の辺）からスタートします。次に、頂点1だけを経由する場合を考えると、直接の辺よりも、頂点1を経由した方が短い経路が見つかる可能性があります。この更新により、「頂点1までを経由する」という条件下での最短経路が求まります。
さらに、頂点2を経由する場合を考えます。この時、既に「頂点1までを経由する」という条件下での最短経路が求まっているので、頂点2を経由することで、さらに短い経路が見つかる可能性があります（頂点1と2の両方を経由する経路も含む）。
このように、「経由してよい頂点」を1つずつ増やしていくことで、考慮できる経路のパターンが段階的に増えていき、最終的には全ての頂点を経由する可能性を考慮した最短経路が求まるのです。
ワーシャル・フロイド法のアルゴリズム
グラフの頂点数を n とします。ワーシャル・フロイド法の具体的な手順は以下の通りです。
手順1: 初期化
n x nの距離行列distを作成します。dist[i][j]を、頂点iからjへの直接の辺のコストで初期化します。- 辺が存在しない場合は、
dist[i][j] = INF(無限大) とします。 dist[i][i] = 0(自身への距離は0) とします。
- 辺が存在しない場合は、
手順2: 最短距離の更新
- 3重ループを用いて
distを更新します。
k: 1 から n までのすべての頂点 (経由する頂点) i: 1 から n までのすべての頂点 (始点) j: 1 から n までのすべての頂点 (終点)
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])を計算します。
具体的な計算例（東京、名古屋、大阪、福岡間の移動）
以下のグラフを例に、ワーシャル・フロイド法の動作を具体的に見ていきましょう (都市は0-indexed)。
都市: 0 (東京), 1 (名古屋), 2 (大阪), 3 (福岡) 移動手段と所要時間: 0 (東京) -> 1 (名古屋) : 新幹線で 100分 0 (東京) -> 3 (福岡) : 飛行機で 120分 1 (名古屋) -> 2 (大阪) : 新幹線で 60分 2 (大阪) -> 3 (福岡) : 新幹線で 150分
このグラフを、以下のような隣接行列で表します (単位: 分)。
graph = [
[0, 100, INF, 120],
[INF, 0, 60, INF],
[INF, INF, 0, 150],
[INF, INF, INF, 0]
]
1. 初期化
このグラフの初期状態の距離行列 dist は以下のようになります。
dist = [
[0, 100, INF, 120],
[INF, 0, 60, INF],
[INF, INF, 0, 150],
[INF, INF, INF, 0]
]
2. 更新 (k=0, 東京経由)
k = 0 (東京を経由する場合) の更新を行います。
i=1 (名古屋),j=2 (大阪)の場合:dist[1][2] = min(dist[1][2], dist[1][0] + dist[0][2])dist[1][2] = min(60, INF + INF) = 60(変化なし)
i=1 (名古屋),j=3 (福岡)の場合:dist[1][3] = min(dist[1][3], dist[1][0] + dist[0][3])dist[1][3] = min(INF, INF + 120) = INF(変化なし)
- 他の都市間の組み合わせでも変化はありません。
3. 更新 (k=1, 名古屋経由)
次に、k = 1 (名古屋を経由する場合) の更新を行います。
i=0 (東京),j=2 (大阪)の場合:dist[0][2] = min(dist[0][2], dist[0][1] + dist[1][2])dist[0][2] = min(INF, 100 + 60) = 160(東京→名古屋→大阪: 160分)
i=0(東京),j=3(福岡)の場合dist[0][3] = min(dist[0][3], dist[0][1] + dist[1][3])dist[0][3] = min(120, 100 + INF) = 120
この時点で、東京から大阪への最短所要時間が、直行便がないため無限大(INF)だったのが、名古屋経由で160分と計算されました。
4. 更新(k = 2,大阪経由)
次に、k = 2 (大阪を経由する場合)の更新を行います。
i=0(東京), j=3(福岡)の場合dist[0][3] = min(dist[0][3], dist[0][2] + dist[2][3])dist[0][3] = min(120, 160 + 150) = 120
i=1(名古屋), j=3(福岡)の場合dist[1][3] = min(dist[1][3], dist[1][2] + dist[2][3])dist[1][3] = min(INF, 60+150) = 210
この時点で、名古屋から福岡への最短所要時間が、乗り継ぎがないため無限大(INF)だったのが、大阪経由で210分と計算されました。
5. 更新 (k=3, 福岡経由)
最後に k = 3 (福岡を経由する場合)ですが、このケースでは、福岡経由でより短くなる経路は存在しません。
最終的な dist は以下のようになります。
dist = [
[0, 100, 160, 120], # 東京
[INF, 0, 60, 210], # 名古屋
[INF, INF, 0, 150], # 大阪
[INF, INF, INF, 0] # 福岡
]
Python による実装例
1. 基本的な実装
まずは、最もシンプルなワーシャル・フロイド法の実装を示します。
INF = float('inf') # 無限大を表す値 def warshall_floyd(graph): """ ワーシャル・フロイド法で全点対間最短経路を計算する Args: graph: 隣接行列形式のグラフ (2次元リスト) graph[i][j] は頂点iからjへの辺のコスト。 辺が存在しない場合は INF。 Returns: 全点対間最短経路の距離行列 (2次元リスト) """ n = len(graph) dist = [row[:] for row in graph] # graph のコピーを作成 for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) return dist
与えられた隣接行列 graph をもとに、dist[i][j] には、頂点 i から頂点 j への最短経路のコストを格納します。
dist[i][k] + dist[k][j] は、頂点 i から頂点 k を経由して頂点 j へ至る経路のコストを表します。
min(dist[i][j], dist[i][k] + dist[k][j])とすることで、より小さいコストの経路があれば更新します。
2. 入力グラフの例
# グラフの隣接行列表現 (0-indexed) graph = [ [0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0] ]
graph[i][j]は、頂点iから頂点jへの辺のコストを表します。INFは辺が存在しないことを示します。
3. 実行と結果の確認
result = warshall_floyd(graph) # 結果の表示 (見やすく整形) print("全点対間最短経路:") for row in result: print(row)
上記のコードではwarshall_floyd関数にgraphを渡し、全頂点間の最短距離を計算しています。
結果は2次元リストとして出力され、各要素result[i][j]が頂点iから頂点jへの最短距離を表します。
4. 負の閉路の検出
ワーシャル・フロイド法は、負の閉路 (合計コストが負になる閉路) が存在する場合も検出できます。
def warshall_floyd_with_negative_cycle_detection(graph): """ ワーシャル・フロイド法で全点対間最短経路を計算し、負の閉路を検出する Args: graph: 隣接行列形式のグラフ Returns: (dist, has_negative_cycle): dist: 全点対間最短経路の距離行列 has_negative_cycle: 負の閉路が存在する場合は True、そうでなければ False """ n = len(graph) dist = [row[:] for row in graph] for k in range(n): for i in range(n): for j in range(n): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) # 負の閉路の検出: 自身への距離が負になる頂点が存在するか確認 has_negative_cycle = False for i in range(n): if dist[i][i] < 0: has_negative_cycle = True break return dist, has_negative_cycle
warshall_floyd_with_negative_cycle_detection関数では、最短経路の計算後、dist[i][i] (頂点 i から自身への距離) が 0 より小さいかどうかを確認します。
もし dist[i][i] < 0 となる頂点 i が存在すれば、それはグラフ内に負の閉路が存在することを意味します。
5. 実用的な関数
def format_shortest_paths(dist): """ 全点対間最短経路の距離行列を見やすい表形式の文字列にする Args: dist: 全点対間最短経路の距離行列 (2次元リスト) Returns: 表形式の文字列 """ n = len(dist) header = " " + " ".join([f"{i:2}" for i in range(n)]) + "\n" separator = "----" + "---" * n + "\n" rows = [] for i, row in enumerate(dist): row_str = f"{i:2} | " + " ".join([f"{x:2}" if x != INF else "∞ " for x in row]) rows.append(row_str) return header + separator + "\n".join(rows) # 使用例 graph = [ [0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0] ] dist, has_negative_cycle = warshall_floyd_with_negative_cycle_detection(graph) if has_negative_cycle: print("負の閉路が検出されました。") else: print("全点対間最短経路:") print(format_shortest_paths(dist))
format_shortest_paths関数は、最短経路の結果を見やすい表形式で出力するための補助関数です。
最後に
他の最短経路アルゴリズムについても下記の記事で解説しています。
[PR] 数理最適化について気軽に学べるUdemyコースや書籍など
