Petua reka bentuk algoritma PHP: Bagaimana untuk menggunakan algoritma Floyd-Warshall untuk menyelesaikan masalah laluan terpendek bagi graf?

Kemahiran reka bentuk algoritma PHP: Bagaimana untuk menggunakan algoritma Floyd-Warshall untuk menyelesaikan masalah laluan terpendek bagi graf?

Ikhtisar:
Dalam teori graf, masalah laluan terpendek ialah masalah algoritma klasik yang melibatkan mencari laluan terpendek antara dua bucu dalam graf terarah atau tidak terarah. Algoritma Floyd-Warshall ialah algoritma pengaturcaraan dinamik klasik yang digunakan untuk menyelesaikan masalah ini. Artikel ini akan memperkenalkan secara terperinci cara melaksanakan algoritma Floyd-Warshall menggunakan PHP.

Pengenalan algoritma Floyd-Warshall:
Algoritma Floyd-Warshall ialah algoritma yang menyelesaikan masalah laluan terpendek dengan secara berulang membandingkan panjang laluan terpendek antara semua bucu dalam graf. Ia menggunakan tatasusunan dua dimensi untuk menyimpan panjang laluan terpendek antara bucu dan mengemas kini tatasusunan ini dalam setiap lelaran. Akhirnya, kita boleh mendapatkan laluan terpendek antara semua bucu.

Pelaksanaan kod:
Pertama, kita perlu mencipta tatasusunan dua dimensi N x N, dengan N mewakili bilangan bucu dalam graf. Setiap elemen dalam tatasusunan mewakili jarak antara dua bucu, atau jika tiada tepi antara dua bucu, jaraknya ditetapkan kepada infiniti. Kodnya kelihatan seperti ini:

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

Seterusnya, kita perlu menentukan graf sampel untuk menguji algoritma kita. Kami menggunakan matriks bersebelahan untuk mewakili struktur graf, menyimpan jarak antara bucu dalam tatasusunan dua dimensi. Kod sampel adalah seperti berikut:

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

Dalam graf sampel di atas, INF bermakna tiada tepi antara dua bucu, dan kita boleh menetapkan jaraknya kepada nilai yang sangat besar. Sekarang, kita boleh memanggil fungsi floydWarshall untuk mengira tatasusunan laluan terpendek. Kodnya kelihatan seperti ini:

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

Menjalankan kod di atas, kita akan mendapat hasil berikut:

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

Hasil di atas menunjukkan panjang laluan terpendek antara semua bucu dalam graf. Antaranya, INF bermaksud tiada sambungan laluan antara dua bucu.

Ringkasan:
Artikel ini memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma Floyd-Warshall untuk menyelesaikan masalah laluan terpendek bagi graf. Dengan menggunakan idea pengaturcaraan dinamik, kita boleh mencari panjang laluan terpendek antara semua bucu dalam graf dengan kerumitan masa O(N^3). Dengan menggunakan teknik reka bentuk algoritma secara rasional, kita boleh menggunakan algoritma ini dengan cepat dan cekap dalam menyelesaikan masalah praktikal.

Di atas ialah pengenalan kepada kemahiran reka bentuk algoritma PHP: cara menggunakan algoritma Floyd-Warshall untuk menyelesaikan masalah laluan terpendek bagi graf saya harap ia akan membantu anda.

Atas ialah kandungan terperinci Petua reka bentuk algoritma PHP: Bagaimana untuk menggunakan algoritma Floyd-Warshall untuk menyelesaikan masalah laluan terpendek bagi graf?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!