Conseils de conception d'algorithme PHP : Comment utiliser l'algorithme de Dijkstra pour résoudre le problème du chemin le plus court à source unique ?

Compétences en conception d'algorithmes PHP : Comment utiliser l'algorithme de Dijkstra pour résoudre le problème du chemin le plus court à source unique ?

Introduction :

En informatique, l'algorithme de Dijkstra est un algorithme classique utilisé pour résoudre le problème du chemin le plus court depuis un point source unique vers tous les autres points du graphique. Dans le développement réel, nous devons souvent résoudre le problème du chemin le plus court dans les sites Web ou les applications, comme trouver l'itinéraire de transport le plus court ou le chemin de navigation optimal entre deux endroits. Cet article présentera comment utiliser PHP pour implémenter l'algorithme de Dijkstra et donnera des exemples de code spécifiques.

1. Introduction à l'algorithme de Dijkstra

L'algorithme de Dijkstra est un algorithme glouton utilisé pour résoudre le problème du plus court chemin à source unique dans les graphes orientés pondérés. L'idée de base de cet algorithme est de partir du point source et de déterminer progressivement le chemin le plus court du point source à chaque sommet. Pendant l'exécution de l'algorithme, la distance du chemin le plus court et les sommets prédécesseurs de chaque sommet sont continuellement mis à jour en maintenant un tableau de distances.

Les étapes de l'algorithme sont les suivantes :

1. Initialisez le tableau de distance, définissez la distance du point source sur 0 et définissez la distance des autres points à l'infini.
2. Sélectionnez la plus petite valeur du tableau de distance comme nœud actuel et marquez le nœud comme visité.
3. Mettez à jour la distance de chemin la plus courte des nœuds adjacents du nœud actuel. Si un chemin plus court est trouvé, mettez à jour le tableau de distance et les sommets prédécesseurs.
4. Répétez les étapes 2 et 3 jusqu'à ce que tous les nœuds soient visités ou qu'il n'y ait plus de valeurs actualisables dans le tableau de distance.

2. Implémentation PHP de l'algorithme Dijkstra

Ce qui suit est un exemple de code pour implémenter l'algorithme Dijkstra en utilisant PHP :

<?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] . "
";
}
?>

Le code ci-dessus définit d'abord une constante infinie INF, puis implémente la fonction dijkstra, qui reçoit une matrice de contiguïté. représentation Le graphique et le point source sont pris comme paramètres, et un tableau contenant la distance la plus courte entre le point source et l'autre sommet est renvoyé.

Dans le programme principal, un graphique représenté par une matrice de contiguïté est utilisé pour tester la fonction dijkstra. Enfin, la distance la plus courte entre chaque sommet et le point source est obtenue via un parcours de boucle.

Conclusion :

Cet article présente comment utiliser PHP pour implémenter l'algorithme de Dijkstra afin de résoudre le problème du chemin le plus court à source unique et donne des exemples de code spécifiques. L'algorithme de Dijkstra est l'un des algorithmes couramment utilisés pour résoudre les problèmes de chemin le plus court et peut être appliqué à de nombreux problèmes pratiques. J'espère que le contenu de cet article sera utile pour comprendre et appliquer l'algorithme de Dijkstra.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!