PHP で Floyd-Warshall アルゴリズムを使用して最短経路検索を実装する方法

コンピューター サイエンスの分野では、フロイド ウォーシャル アルゴリズム (略して FW アルゴリズム) は、すべてのノード ペアの最短経路問題を解く動的計画アルゴリズムです。すべてのエッジの重みが正または負である有向グラフまたは無向グラフを解くことができ、時間と空間の両方の複雑さの最適化問題があります。

PHP では、FW アルゴリズムを実装する方法が数多くあります。その 1 つは、2 次元配列を使用して心臓の隣接行列を表す方法です。具体的な手順は次のとおりです。

1. 隣接行列の構築

隣接行列は、各要素が 2 つの頂点間の距離を表す 2 次元配列です。 。 2 つの頂点間に接続がない場合、値は無限大になります。 PHP では、隣接行列は次の方法で初期化できます。

// Initialize an empty adjacency matrix
$adjMatrix = [];

// Fill the adjacency matrix with infinite values
for($i=0; $i<$n; $i++) {
  for($j=0; $j<$n; $j++) {
    $adjMatrix[$i][$j] = INF;
  }
}

// Assign values to the adjacency matrix
for($i=0; $i<count($edges); $i++) {
  $source = $edges[$i][0];
  $dest = $edges[$i][1];
  $weight = $edges[$i][2];
  $adjMatrix[$source][$dest] = $weight;
}

このうち、$n はグラフ全体のノードの数を表し、$edges は開始点を含むエッジの数の配列を表します。各エッジの終点と重み。

2. 行列 dp 配列の構築

dp 配列も 2 次元配列であり、各要素は開始点から次の点までの最短パスの長さを表します。ポイント。初期化に隣接行列を使用します:

$dp = $adjMatrix;

3. FW アルゴリズムを使用して最短パスを検索します

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

$k、$i、$j$ はそれぞれ行と列を表しますノード行列の添字内。

4. 出力結果

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

上記は、PHP で FW アルゴリズムを使用して最短パスを見つけるプロセスです。実際のアプリケーションでは、実際のニーズを満たすために、特定の状況に応じてアルゴリズムの最適化とパフォーマンスのチューニングを実行する必要があることに注意してください。

以上がPHP で Floyd-Warshall アルゴリズムを使用して最短経路検索を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。