ワーシャル・フロイド法は、グラフ理論において重要なアルゴリズムの1つです。このアルゴリズムは、全ての頂点間の最短経路を求めることができます。この記事では、ワーシャル・フロイド法の解説とPythonでの実装例について解説します。
ワーシャル・フロイド法とは
ワーシャル・フロイド法は、動的計画法の1つです。これは、最適解を求めるために、小さな問題から順番に解決していくアルゴリズムです。ワーシャル・フロイド法は、すべての頂点間の最短経路を求める問題を解決するために使用されます。このアルゴリズムは、負の辺を含むグラフでも使用できます。ワーシャル・フロイド法のアルゴリズムは、以下の手順で実行されます。
- 初期化：グラフ上のすべての頂点の間の距離を初期化します。
- ループ：すべての頂点について、他のすべての頂点までの最短距離を更新します。
- 最短距離の更新：更新された距離を使用して、各頂点の他の頂点への最短距離を更新します。
Pythonでの実装例
Pythonでのワーシャル・フロイド法の実装例以下は、Pythonでワーシャル・フロイド法を実装する例です。
INF = 99999 def floyd_warshall(graph): n = len(graph) dist = [[INF for j in range(n)] for i in range(n)] for i in range(n): for j in range(n): dist[i][j] = graph[i][j] 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 = [[0, 5, INF, 10], [INF, 0, 3, INF], [INF, INF, 0, 1], [INF, INF, INF, 0]] print(floyd_warshall(graph))
上記のコードでは、INFという大きな値を使用して、初期距離を設定します。次に、すべての頂点間の距離を計算します。これは、すべての頂点を通る可能性がある最短経路を計算するために、小さなサブプロブレムを順番に解決していく動的計画法のアプローチです。最初に、各頂点から自分自身への距離は0であるため、dist[i][i] = 0 とします。次に、すべての辺の距離をdist[i][j]に設定します。この後、kを通過するすべての最短経路を計算するために、iからjへの最短距離は、iからkへの最短距離とkからjへの最短距離の和のうち最小値を選択します。これは、iからjへの経路にkを挿入することで、より短い経路が見つかる可能性があるためです。この処理を繰り返すことで、すべての頂点間の最短経路が求められます。上記のコードでは、入力グラフを2次元のリストとして受け取り、距離行列を返します。例えば、入力グラフは以下のように表されています。
0 5 INF 10 INF 0 3 INF INF INF 0 1 INF INF INF 0
このグラフは、4つの頂点を持ち、頂点0から頂点3への最短距離は9、頂点1から頂点2への最短距離は3です。このグラフを入力として、floyd_warshall関数を実行すると、以下のような結果が返されます。
[ [0, 5, 8, 9], [INF, 0, 3, 4], [INF, INF, 0, 1], [INF, INF, INF, 0] ]
この結果から、すべての頂点間の最短距離が求められていることがわかります。
まとめ
ワーシャル・フロイド法は、すべての頂点間の最短経路を求める問題を解決するために使用されるアルゴリズムです。このアルゴリズムは、動的計画法を用いて、小さなサブプロブレムから順番に解決していくアプローチをとります。Pythonでのワーシャル・フロイド法の実装は、簡単に行うことができ、グラフを2次元のリストとして受け取り、距離行列を返します。このアルゴリズムは、負の辺を含むグラフでも使用できるため、幅広いアプリケーションに使用されています。他の最短経路アルゴリズムについては下記の記事で解説しています。
