PHP에서 Floyd-Warshall 알고리즘을 사용하여 최단 경로 찾기를 구현하는 방법

컴퓨터 과학 분야에서 Floyd-Warshall 알고리즘(줄여서 FW 알고리즘)은 모든 노드 쌍에 대한 최단 경로 문제를 해결하는 동적 프로그래밍 알고리즘입니다. 모든 간선의 가중치가 양수이거나 음수이고 시간 및 공간 복잡도 최적화 문제가 모두 있는 방향성 또는 방향성 그래프를 해결할 수 있습니다.

PHP에서는 FW 알고리즘을 구현하는 방법이 여러 가지가 있는데, 그 중 하나는 2차원 배열을 사용하여 심장의 인접 행렬을 표현하는 것입니다. 구체적인 단계는 다음과 같습니다.

1. 인접 행렬 만들기

인접 행렬은 각 요소가 두 정점 사이의 거리를 나타내는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!