Floyd-Warshallアルゴリズムの原理は比較的単純です。アルゴリズムは、すべての頂点のペアに対して、それらを直接結ぶ辺の距離を初期値として設定します。そして、すべての頂点を経由する経路の距離を順次更新していきます。具体的には、各頂点を中継点として考え、その中継点を経由する経路の距離がより短くなる場合には、距離を更新します。この更新処理を繰り返すことで、最終的にすべての頂点間の最短経路の距離が求められます。
以下に、Floyd-Warshallアルゴリズムの具体的な実装方法を示します。
def floyd_warshall(graph):
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
elif graph[i][j] != float('inf'):
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上記のコードは、入力として隣接行列形式のグラフを受け取り、最短経路の距離を表す2次元リストを返します。距離が不明な場合はfloat('inf')として初期化されます。