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

#🎜🎜 Petua reka bentuk algoritma #PHP: Bagaimana untuk menggunakan algoritma Dijkstra untuk menyelesaikan masalah laluan terpendek sumber tunggal?

Pengenalan:

Dalam sains komputer, algoritma Dijkstra ialah algoritma klasik yang digunakan untuk menyelesaikan masalah laluan terpendek dari satu titik sumber ke semua titik lain dalam graf. Dalam pembangunan sebenar, kita selalunya perlu menangani masalah laluan terpendek dalam laman web atau aplikasi, seperti mencari laluan pengangkutan terpendek atau laluan navigasi optimum antara dua tempat. Artikel ini akan memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma Dijkstra dan memberikan contoh kod khusus.

1. Pengenalan kepada algoritma Dijkstra

Algoritma Dijkstra ialah algoritma tamak yang digunakan untuk menyelesaikan masalah laluan terpendek sumber tunggal dalam graf berwajaran. Idea asas algoritma ini adalah bermula dari titik sumber dan secara beransur-ansur menentukan laluan terpendek dari titik sumber kepada satu sama lain. Semasa pelaksanaan algoritma, jarak laluan terpendek dan bucu pendahulu bagi setiap bucu sentiasa dikemas kini dengan mengekalkan tatasusunan jarak.

Langkah algoritma adalah seperti berikut:

Mulakan tatasusunan jarak, tetapkan jarak titik sumber kepada 0, dan tetapkan jarak titik lain kepada infiniti.
1. Pilih nilai terkecil dalam tatasusunan jarak sebagai nod semasa dan tandai nod sebagai dilawati.
2. Kemas kini jarak laluan terpendek bagi nod bersebelahan nod semasa Jika laluan yang lebih pendek ditemui, kemas kini tatasusunan jarak dan bucu pendahulu.
3. Ulang langkah 2 dan 3 sehingga semua nod telah dilawati atau tiada nilai yang boleh dikemas kini dalam tatasusunan jarak.

2. Pelaksanaan PHP algoritma Dijkstra

Berikut ialah contoh kod menggunakan PHP untuk melaksanakan algoritma Dijkstra:

<?php
// 定义无穷大常量
define('INF', PHP_INT_MAX);

function dijkstra($graph, $source) {
    $numVertices = count($graph);
    
    // 初始化距离数组和标记数组
    $dist = array_fill(0, $numVertices, INF);
    $visited = array_fill(0, $numVertices, false);
    
    // 源点到源点的距离为0
    $dist[$source] = 0;
    
    // 更新距离数组和前驱顶点
    for ($i = 0; $i < $numVertices - 1; $i++) {
        // 找到距离数组中最小的值
        $minDist = INF;
        $minIndex = -1;
        
        for ($j = 0; $j < $numVertices; $j++) {
            if (!$visited[$j] && $dist[$j] <= $minDist) {
                $minDist = $dist[$j];
                $minIndex = $j;  
            }
        }
        
        // 将最小值标记为已访问
        $visited[$minIndex] = true;
        
        // 更新邻接节点的距离和前驱顶点
        for ($k = 0; $k < $numVertices; $k++) {
            if (!$visited[$k] && $graph[$minIndex][$k] && 
                $dist[$minIndex] !== INF && 
                $dist[$minIndex] + $graph[$minIndex][$k] < $dist[$k]) {
                $dist[$k] = $dist[$minIndex] + $graph[$minIndex][$k];
            }
        }
    }
    
    return $dist;
}

// 图的邻接矩阵表示
$graph = array(
    array(0, 4, 0, 0, 0, 0, 0, 8, 0),
    array(4, 0, 8, 0, 0, 0, 0, 11, 0),
    array(0, 8, 0, 7, 0, 4, 0, 0, 2),
    array(0, 0, 7, 0, 9, 14, 0, 0, 0),
    array(0, 0, 0, 9, 0, 10, 0, 0, 0),
    array(0, 0, 4, 14, 10, 0, 2, 0, 0),
    array(0, 0, 0, 0, 0, 2, 0, 1, 6),
    array(8, 11, 0, 0, 0, 0, 1, 0, 7),
    array(0, 0, 2, 0, 0, 0, 6, 7, 0)
);

$source = 0; // 源点

$dist = dijkstra($graph, $source);

echo "顶点        最短距离
";
for ($i = 0; $i < count($dist); $i++) {
    echo $i . "        " . $dist[$i] . "
";
}
?>

#🎜🎜 kod di atas dahulu INF pemalar tak terhingga ditakrifkan, dan kemudian fungsi dijkstra dilaksanakan Fungsi ini menerima graf yang diwakili oleh matriks bersebelahan dan titik sumber sebagai parameter, dan mengembalikan tatasusunan yang memegang jarak terpendek dari titik sumber kepada satu sama lain. puncak.

Dalam atur cara utama, graf yang diwakili oleh matriks bersebelahan digunakan untuk menguji fungsi dijkstra. Akhir sekali, jarak terpendek dari setiap bucu ke titik sumber adalah output melalui lintasan gelung.

Kesimpulan:

Artikel ini memperkenalkan cara menggunakan PHP untuk melaksanakan algoritma Dijkstra untuk menyelesaikan masalah laluan terpendek sumber tunggal, dan memberikan contoh kod khusus. Algoritma Dijkstra ialah salah satu algoritma yang biasa digunakan untuk menyelesaikan masalah laluan terpendek dan boleh digunakan untuk banyak masalah praktikal. Saya berharap kandungan artikel ini akan membantu untuk memahami dan menggunakan algoritma Dijkstra.

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