Floyd-Warshall アルゴリズムと Warshall アルゴリズムの推移閉包実装を比較する

推移的閉包の 2 つのアルゴリズムを理解します: フロイド ウォーシャル アルゴリズムとウォーシャル アルゴリズム

推移的閉包は、グラフ理論の重要な概念であり、グラフ推移のノードを記述します。彼らの間の関係。推移閉包アルゴリズムは、グラフ内の点 A から点 B へのパスが存在するかどうかを迅速に判断するのに役立ちます。

推移的閉包アルゴリズムには、Floyd-Warshall アルゴリズムと Warshall アルゴリズムという 2 つの一般的に使用されるアルゴリズムがあります。どちらも推移閉包を効率的に計算できますが、実装の詳細とパフォーマンスが異なります。

1. フロイド-ウォーシャル アルゴリズム

フロイド-ウォーシャル アルゴリズムは、グラフ内の任意の 2 点間の最短経路を計算するために使用される動的プログラミング アルゴリズムです。 Floyd-Warshall アルゴリズムは、グラフ内のすべてのノードを走査することによってノード間の距離を継続的に更新します。最終的な行列では、ノード i からノード j へのパスがある場合、行列内の (i, j) 位置の値は 1 になります。 、それ以外の場合は 0。

次は、フロイド-ウォーシャル アルゴリズムのサンプル コードです。

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] != 0:
                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. ウォーシャル アルゴリズム

ウォーシャル アルゴリズムは、行列演算に基づくアルゴリズムです。グラフ内の任意の 2 点間にパスがあるかどうかを計算するために使用されます。ブール行列を継続的に更新することにより、グラフ内の推移的な関係が決定されます。

次は、Warshall アルゴリズムのサンプル コードです:

def warshall(graph):
    n = len(graph)
    reachable = [[False] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if graph[i][j] != 0:
                reachable[i][j] = True

    for k in range(n):
        for i in range(n):
            for j in range(n):
                reachable[i][j] = reachable[i][j] or (reachable[i][k] and reachable[k][j])

    return reachable

上記のサンプル コードを通じて、Floyd-Warshall アルゴリズムと Warshall アルゴリズムの具体的な実装を理解します。どちらも推移閉包の計算効率が高くなりますが、フロイド・ウォーシャル アルゴリズムは有向グラフ内の任意の 2 点間の最短経路を計算するのに適しており、ウォーシャル アルゴリズムはグラフ内の任意の 2 点がその経路であるかどうかを判断するのに適しています。存在します。

最短経路を計算する必要がある場合は、Floyd-Warshall アルゴリズムを使用でき、経路が存在するかどうかだけを判断する必要がある場合は、Warshall アルゴリズムを選択できます。適切なアルゴリズムを選択することで、グラフ理論の問題における推移閉包の計算をより効率的に解くことができます。

以上がFloyd-Warshall アルゴリズムと Warshall アルゴリズムの推移閉包実装を比較するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。