Petua reka bentuk algoritma PHP: Bagaimana untuk menggunakan algoritma Bellman-Ford untuk menyelesaikan masalah laluan terpendek sumber tunggal?

Kemahiran reka bentuk algoritma PHP: Bagaimana untuk menggunakan algoritma Bellman-Ford untuk menyelesaikan masalah laluan terpendek sumber tunggal?

Ikhtisar:
Algoritma Bellman-Ford ialah algoritma klasik untuk menyelesaikan masalah laluan terpendek sumber tunggal dalam graf. Ia boleh mengendalikan graf dengan tepi berat negatif dan dapat mengesan kehadiran kitaran berat negatif. Artikel ini akan memperkenalkan cara melaksanakan algoritma Bellman-Ford menggunakan PHP dan memberikan contoh kod.

Pengetahuan latar belakang:
Sebelum kita memahami algoritma Bellman-Ford secara mendalam, kita perlu memahami beberapa pengetahuan teori graf asas.

1. Perwakilan graf:
   Graf terdiri daripada nod (bucu) dan tepi (tepi). Nod boleh diwakili sebagai nombor atau rentetan, dan tepi boleh diwakili sebagai tupel yang mengandungi dua nod dan maklumat berat.
2. Kaedah perwakilan graf:
   Matriks bersebelahan dan senarai bersebelahan ialah dua kaedah perwakilan graf biasa.
3. Matriks bersebelahan: Gunakan tatasusunan dua dimensi untuk mewakili hubungan sambungan antara nod. Jika terdapat tepi antara nod i dan nod j, nilai dalam baris i dan lajur j dalam matriks bersebelahan ialah berat tepi; jika tiada tepi, nilai pada kedudukan ini adalah infiniti (inf).
4. Senarai bersebelahan: Untuk setiap nod, senarai terpaut digunakan untuk menyimpan maklumat tentang tepi yang disambungkan kepadanya.
5. Masalah laluan terpendek sumber tunggal:
   Memandangkan graf terarah, cari laluan terpendek dari satu nod sumber ke semua nod lain.

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

<?php

class Graph {
    private $vertices;
    private $edges;

    public function __construct($vertices) {
        $this->vertices = $vertices;
        $this->edges = [];
    }

    public function addEdge($start, $end, $weight) {
        $this->edges[] = [$start, $end, $weight];
    }

    public function bellmanFord($source) {
        $distance = [];
        $predecessor = [];

        // 设置源节点到其他所有节点的初始距离为无穷大
        foreach ($this->vertices as $vertex) {
            $distance[$vertex] = INF;
            $predecessor[$vertex] = null;
        }

        $distance[$source] = 0;

        // 对每个节点进行松弛操作
        for ($i = 0; $i < count($this->vertices) - 1; $i++) {
            foreach ($this->edges as $edge) {
                $u = $edge[0];
                $v = $edge[1];
                $w = $edge[2];

                if ($distance[$u] != INF && $distance[$u] + $w < $distance[$v]) {
                    $distance[$v] = $distance[$u] + $w;
                    $predecessor[$v] = $u;
                }
            }
        }

        // 检测负权环
        foreach ($this->edges as $edge) {
            $u = $edge[0];
            $v = $edge[1];
            $w = $edge[2];

            if ($distance[$u] != INF && $distance[$u] + $w < $distance[$v]) {
                echo "图中存在负权环";
                return;
            }
        }

        // 输出最短路径结果
        foreach ($this->vertices as $vertex) {
            echo "节点" . $vertex . "的最短路径长度为： " . $distance[$vertex] . "，路径为： ";
            $path = [];
            $current = $vertex;

            while ($current != $source) {
                array_unshift($path, $current);
                $current = $predecessor[$current];
            }

            array_unshift($path, $source);
            echo implode(" -> ", $path) . "
";
        }
    }
}

$graph = new Graph(["A", "B", "C", "D", "E"]);
$graph->addEdge("A", "B", 4);
$graph->addEdge("A", "C", 1);
$graph->addEdge("C", "B", -3);
$graph->addEdge("B", "D", 2);
$graph->addEdge("D", "E", 3);
$graph->addEdge("E", "D", -5);

$graph->bellmanFord("A");

Analisis kod:
Pertama, kami mencipta kelas Graf untuk mewakili graf, yang merangkumi nod dan tepi maklumat. Maklumat tepi graf disimpan dalam tatasusunan tepi.

Gunakan kaedah addEdge untuk menambah maklumat tepi.

Kaedah bellmanFord melaksanakan algoritma Bellman-Ford. Pertama, kita memulakan tatasusunan jarak dan tatasusunan nod pendahulu. Kemudian, tetapkan jarak nod sumber kepada 0. Seterusnya, lakukan kitaran V-1 pada setiap nod, dengan V ialah bilangan nod. Dalam gelung, kami menyemak setiap tepi dan melonggarkannya jika terdapat laluan yang lebih pendek. Akhir sekali, kami menyemak sama ada terdapat kitaran berat negatif, dan jika ya, cetak mesej segera. Akhir sekali, kami mengeluarkan laluan terpendek dan panjang laluan untuk setiap nod.

Dalam kod sampel, kami mencipta graf yang mengandungi 5 nod, yang mengandungi beberapa tepi berat positif dan negatif. Akhir sekali, kami menggunakan kaedah bellmanFord, menggunakan "A" sebagai nod sumber, untuk mengira laluan terpendek.

Ringkasan:
Artikel ini memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma Bellman-Ford untuk menyelesaikan masalah laluan terpendek sumber tunggal dalam graf. Algoritma Bellman-Ford sesuai untuk graf yang mengandungi tepi berat negatif dan boleh mengesan kewujudan kitaran berat negatif. Dengan memahami kaedah perwakilan graf, memahami prinsip algoritma Bellman-Ford, dan mempraktikkannya dengan kod sampel, saya percaya pembaca akan mempunyai pemahaman yang lebih mendalam tentang algoritma.

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