PHP アルゴリズム設計のヒント: グラフの最短経路問題を解決するためにフロイド・ウォーシャル アルゴリズムを使用する方法

PHP アルゴリズム設計のヒント: フロイド・ウォーシャル アルゴリズムを使用してグラフの最短経路問題を解決するにはどうすればよいですか?

概要:
グラフ理論における最短経路問題は、有向グラフまたは無向グラフの 2 つの頂点間の最短経路を見つけることを含む古典的なアルゴリズム問題です。フロイド-ウォーシャル アルゴリズムは、この問題を解決するために使用される古典的な動的計画法アルゴリズムです。この記事では、PHPを使用してフロイド・ウォーシャルアルゴリズムを実装する方法を詳しく紹介します。

フロイド-ウォーシャル アルゴリズムの概要:
フロイド-ウォーシャル アルゴリズムは、グラフ内のすべての頂点間の最短パスの長さを反復的に比較することによって、最短パスの問題を解決するアルゴリズムです。 2 次元配列を使用して頂点間の最短パス長を保存し、反復ごとにこの配列を更新します。最後に、すべての頂点間の最短パスを取得できます。

コードの実装:
まず、N x N の 2 次元配列を作成する必要があります。ここで、N はグラフの頂点の数を表します。配列内の各要素は 2 つの頂点間の距離を表します。2 つの頂点間にエッジがない場合、それらの距離は無限大に設定されます。コードは次のようになります。

function floydWarshall($graph) {
    $n = count($graph);
    $dist = $graph;

    for ($k = 0; $k < $n; $k++) {
        for ($i = 0; $i < $n; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($dist[$i][$k] + $dist[$k][$j] < $dist[$i][$j]) {
                    $dist[$i][$j] = $dist[$i][$k] + $dist[$k][$j];
                }
            }
        }
    }

    return $dist;
}

次に、アルゴリズムをテストするためのサンプル グラフを定義する必要があります。隣接行列を使用してグラフの構造を表現し、頂点間の距離を 2 次元配列に格納します。サンプル コードは次のとおりです。

$graph = [
    [0, 5, INF, 10],
    [INF, 0, 3, INF],
    [INF, INF, 0, 1],
    [INF, INF, INF, 0]
];

上記のグラフの例では、INF は 2 つの頂点間にエッジがないことを意味し、頂点間の距離を非常に大きな値に設定できます。これで、 floydWarshall 関数を呼び出して最短パス配列を計算できます。コードは次のとおりです。

$result = floydWarshall($graph);

for ($i = 0; $i < count($result); $i++) {
    for ($j = 0; $j < count($result[$i]); $j++) {
        if ($result[$i][$j] == INF) {
            echo "INF ";
        } else {
            echo $result[$i][$j] . " ";
        }
    }
    echo "
";
}

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

0 5 8 9 
INF 0 3 4 
INF INF 0 1 
INF INF INF 0

上記の結果は、グラフ内のすべての頂点間の最短パス長を示しています。このうち INF は 2 つの頂点間にパス接続がないことを意味します。

概要:
この記事では、PHP を使用してフロイド-ウォーシャル アルゴリズムを実装し、グラフの最短経路問題を解決する方法を紹介します。動的計画法の考え方を使用すると、時間計算量 O(N^3) のグラフ内のすべての頂点間の最短経路長を見つけることができます。アルゴリズム設計手法を合理的に使用することで、このアルゴリズムを実際の問題の解決に迅速かつ効率的に適用できます。

上記は、グラフの最短経路問題を解くためにフロイド・ウォーシャルアルゴリズムを使用する方法という、PHP アルゴリズム設計スキルの紹介です。

以上がPHP アルゴリズム設計のヒント: グラフの最短経路問題を解決するためにフロイド・ウォーシャル アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。