Python を使用して Floyd-Warshall アルゴリズムを実装するにはどうすればよいですか?

Python を使用して Floyd-Warshall アルゴリズムを実装するにはどうすればよいですか?

フロイド-ウォーシャル アルゴリズムは、すべてのソース ポイントからすべての目的点までの最短経路問題を解くために使用される古典的なアルゴリズムです。これは、有向グラフまたは負の重みエッジ問題を処理するために使用できる動的プログラミング アルゴリズムです。この記事では、Python を使用して Floyd-Warshall アルゴリズムを実装する方法を紹介し、具体的なコード例を示します。

フロイド・ウォーシャル アルゴリズムの中心的な考え方は、各ノードを中間ノードとして使用し、グラフ内のすべてのノードを走査することにより、ノード間の最短パスを徐々に更新することです。 2 次元行列を使用して、グラフ内のノード間の距離を保存できます。

まず、Floyd-Warshall アルゴリズムを実装する関数を定義する必要があります。以下は、単純なアルゴリズム フレームワークです。

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

このコードは、3 つのネストされたループを使用して、グラフ内の各ノードを処理します。各反復で、距離行列を更新することにより、より短いパスを見つけます。具体的には、ノード i からノード j へのパスがノード k を経由してより短い距離を達成できるかどうかを確認します。そうであれば、距離行列の値を更新します。

この関数を使用する前に、グラフを定義する必要があります。グラフ例の定義は次のとおりです。

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

このグラフ例は、有向グラフの隣接行列表現です。このうち float('inf') は距離が無限大であることを意味し、2 つのノード間に直接のつながりがないことを意味します。

以下では、floydWarshall 関数を呼び出し、パラメータとしてグラフを渡し、最終結果を出力します:

result = floydWarshall(graph)
for row in result:
    print(row)

完全なコードは次のとおりです:

def floydWarshall(graph):
    dist = graph
    num_vertices = len(graph)
    
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

result = floydWarshall(graph)
for row in result:
    print(row)

上記のコードを実行すると、次の出力が得られます。

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]

出力結果は、グラフ内の任意の 2 つのノード間の最短パスを表す 2 次元行列です。たとえば、result[0][2] の値は -2 です。これは、ノード 0 からノード 2 までの最短パス距離が -2 であることを意味します。 2 つのノードに到達できない場合、距離は無限としてマークされます。

この例を通じて、フロイド-ウォーシャル アルゴリズムの実装と使用法を明確に理解できます。この記事がこのアルゴリズムの理解と応用に役立つことを願っています。

以上がPython を使用して Floyd-Warshall アルゴリズムを実装するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。