Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah laluan terpendek graf?

Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah laluan terpendek graf?

Dalam pembangunan sebenar, kita selalunya perlu menyelesaikan masalah laluan terpendek, seperti dalam navigasi peta, penghalaan rangkaian, logistik dan pengedaran, dsb. Algoritma laluan terpendek untuk graf adalah kunci untuk menyelesaikan jenis masalah ini.

Sesuatu graf terdiri daripada satu set bucu dan satu set tepi. Bucu mewakili nod, dan tepi mewakili hubungan antara nod. Masalah laluan terpendek ialah mencari laluan terpendek yang menghubungkan dua nod.

Dalam PHP, kita boleh menggunakan pelbagai algoritma untuk menyelesaikan masalah laluan terpendek, yang paling terkenal ialah algoritma Dijkstra dan algoritma Bellman-Ford. Di bawah ini kami memperkenalkan idea pelaksanaan dan kod sampel kedua-dua algoritma ini.

1. Algoritma Dijkstra:
   Algoritma Dijkstra ialah algoritma yang digunakan secara meluas untuk mengira laluan terpendek dalam graf. Ia menggunakan strategi tamak untuk menentukan laluan terpendek secara beransur-ansur dari nod permulaan kepada nod satu sama lain.

Langkah-langkah algoritma Dijkstra adalah seperti berikut:
1) Tentukan jarak tatasusunan, mewakili jarak terpendek dari nod permulaan ke nod lain, dengan nilai awal ialah infiniti.
2) Tentukan tatasusunan yang dilawati, menunjukkan sama ada nod telah dilawati dan nilai awal adalah palsu.
3) Tetapkan jarak terpendek nod permulaan kepada 0.
4) Ulangi langkah berikut sehingga semua nod telah dilawati:
a) Pilih nod daripada nod yang belum dilawati yang paling hampir dengan nod permulaan.
b) Tandakan nod sebagai dilawati.
c) Kemas kini jarak terpendek antara nod yang bersebelahan dengan nod Jika jarak terpendek yang dikemas kini kurang daripada jarak sebelumnya, kemas kini nilai dalam tatasusunan jarak.
5) Akhirnya dapatkan tatasusunan jarak, dengan jarak[i] mewakili jarak terpendek dari nod permulaan ke nod i.

Berikut ialah contoh kod untuk melaksanakan algoritma Dijkstra menggunakan PHP:

function dijkstra($graph, $startNode) {
    $distances = array();
    $visited = array();

    foreach ($graph as $node => $value) {
        $distances[$node] = INF; // 初始距离设为无穷大
        $visited[$node] = false; // 初始状态为未访问
    }

    $distances[$startNode] = 0; // 起始节点的距离设为0

    while (true) {
        $closestNode = null;

        foreach ($graph[$startNode] as $neighbor => $distance) {
            if (!$visited[$neighbor]) {
                if ($closestNode === null || $distances[$neighbor] < $distances[$closestNode]) {
                    $closestNode = $neighbor;
                }
            }
        }

        if ($closestNode === null) {
            break;
        }

        $visited[$closestNode] = true;

        foreach ($graph[$closestNode] as $key => $value) {
            $distanceToNeighbor = $distances[$closestNode] + $value;
            if ($distanceToNeighbor < $distances[$key]) {
                $distances[$key] = $distanceToNeighbor;
            }
        }
    }

    return $distances;
}

2. Algoritma Bellman-Ford:
   Algoritma Bellman-Ford ialah algoritma klasik untuk menyelesaikan masalah laluan terpendek, yang boleh menangani graf dengan tepi berat negatif.

Langkah-langkah algoritma Bellman-Ford adalah seperti berikut:
1) Tentukan jarak tatasusunan, mewakili jarak terpendek dari nod permulaan ke nod lain, dan nilai awal ialah infiniti.
2) Tetapkan jarak terpendek nod permulaan kepada 0.
3) Ulang langkah berikut sehingga semua tepi mengendur:
a) Semua tepi dilonggarkan, iaitu jarak dipendekkan oleh tepi seterusnya.
b) Kemas kini tatasusunan jarak, dan jika laluan yang lebih pendek ditemui, kemas kini jarak terpendek.
4) Akhir sekali, semak sama ada terdapat gelung berat negatif Jika wujud, ini bermakna terdapat laluan berat negatif yang tidak terhad dalam graf.

Berikut ialah contoh kod menggunakan PHP untuk melaksanakan algoritma Bellman-Ford:

function bellmanFord($graph, $startNode) {
    $numOfVertices = count($graph);
    $distances = array_fill(0, $numOfVertices, INF);
    $distances[$startNode] = 0;

    for ($i = 0; $i < $numOfVertices - 1; $i++) {
        for ($j = 0; $j < $numOfVertices; $j++) {
            for ($k = 0; $k < $numOfVertices; $k++) {
                if ($graph[$j][$k] != INF && $distances[$j] + $graph[$j][$k] < $distances[$k]) {
                    $distances[$k] = $distances[$j] + $graph[$j][$k];
                }
            }
        }
    }

    for ($j = 0; $j < $numOfVertices; $j++) {
        for ($k = 0; $k < $numOfVertices; $k++) {
            if ($graph[$j][$k] != INF && $distances[$j] + $graph[$j][$k] < $distances[$k]) {
                die("图中存在负权回路");
            }
        }
    }

    return $distances;
}

Ringkasan:
Masalah laluan terpendek bagi graf adalah sangat biasa dalam aplikasi praktikal Dengan menguasai dua algoritma Dijkstra dan Bellman-Ford, kami boleh menyelesaikan masalah ini dengan cekap jenis masalah. Mengikut ciri dan keperluan graf, memilih algoritma yang sesuai boleh meningkatkan kecekapan pengiraan dan menjadikan program berprestasi lebih baik. Saya harap pengenalan dalam artikel ini akan membantu semua orang.

Atas ialah kandungan terperinci Idea reka bentuk algoritma PHP: Bagaimana untuk mencapai penyelesaian yang cekap kepada masalah laluan terpendek graf?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!