Bagaimana untuk melaksanakan pencarian laluan terpendek menggunakan algoritma Floyd-Warshall dalam PHP

Dalam bidang sains komputer, algoritma Floyd-Warshall (pendek kata algoritma FW) ialah algoritma pengaturcaraan dinamik yang menyelesaikan masalah laluan terpendek untuk semua pasangan nod. Ia boleh menyelesaikan graf terarah atau tidak terarah di mana pemberat semua tepi adalah positif atau negatif, dan mempunyai kedua-dua masalah pengoptimuman kerumitan masa dan ruang.

Dalam PHP, terdapat banyak cara untuk melaksanakan algoritma FW, salah satunya ialah menggunakan tatasusunan dua dimensi untuk mewakili matriks bersebelahan jantung. Berikut ialah langkah khusus:

1. Bina matriks bersebelahan

Matriks bersebelahan ialah tatasusunan dua dimensi di mana setiap elemen mewakili jarak antara dua bucu. Jika tiada sambungan antara dua bucu, nilainya ialah infiniti. Dalam PHP, matriks bersebelahan boleh dimulakan dengan cara berikut:

// 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;
}

di mana, $n mewakili bilangan nod dalam keseluruhan graf dan $edges mewakili tatasusunan nombor tepi, termasuk titik permulaan, titik akhir dan berat setiap tepi.

2. Bina tatasusunan dp matriks

Tatasusunan dp juga merupakan tatasusunan dua dimensi, di mana setiap elemen mewakili panjang laluan terpendek dari titik permulaan ke titik. Gunakan matriks bersebelahan untuk permulaan:

$dp = $adjMatrix;

3. Gunakan algoritma FW untuk mencari laluan terpendek

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];
      }
    }
  }
}

di mana $k, $i, $j$ masing-masing mewakili subskrip baris dan lajur dalam matriks nod.

4. Output result

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 "
";
}

Di atas adalah proses menggunakan algoritma FW untuk mencari laluan terpendek dalam PHP. Perlu diingat bahawa dalam aplikasi praktikal, pengoptimuman algoritma dan penalaan prestasi perlu dijalankan mengikut situasi tertentu untuk memenuhi keperluan sebenar.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pencarian laluan terpendek menggunakan algoritma Floyd-Warshall dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!