Idées de conception d'algorithmes PHP : Comment parvenir à une solution efficace au problème du chemin le plus court des graphiques ?

Idées de conception d'algorithmes PHP : Comment parvenir à une solution efficace au problème du chemin le plus court des graphiques ?

Dans le développement réel, nous devons souvent résoudre le problème du chemin le plus court, comme dans la navigation cartographique, le routage du réseau, la logistique et la distribution, etc. L’algorithme du plus court chemin pour les graphiques est la clé pour résoudre ce type de problème.

Un graphe se compose d'un ensemble de sommets et d'un ensemble d'arêtes. Les sommets représentent les nœuds et les arêtes représentent les relations entre les nœuds. Le problème du chemin le plus court consiste à trouver le chemin le plus court reliant deux nœuds.

En PHP, nous pouvons utiliser une variété d'algorithmes pour résoudre le problème du chemin le plus court, dont les plus connus sont l'algorithme de Dijkstra et l'algorithme de Bellman-Ford. Ci-dessous, nous présentons respectivement les idées de mise en œuvre et les exemples de codes de ces deux algorithmes.

1. Algorithme de Dijkstra :
   L'algorithme de Dijkstra est un algorithme largement utilisé pour calculer le chemin le plus court dans un graphique. Il utilise une stratégie gloutonne pour déterminer progressivement le chemin le plus court du nœud de départ à l’autre nœud.

Les étapes de l'algorithme de Dijkstra sont les suivantes :
1) Définir un tableau de distances, représentant la distance la plus courte entre le nœud de départ et les autres nœuds, la valeur initiale étant l'infini.
2) Définissez un tableau visité, indiquant si le nœud a été visité, et la valeur initiale est fausse.
3) Définissez la distance la plus courte du nœud de départ sur 0.
4) Répétez les étapes suivantes jusqu'à ce que tous les nœuds aient été visités :
a) Sélectionnez un nœud parmi les nœuds non visités qui est le plus proche du nœud de départ.
b) Marquez le nœud comme visité.
c) Mettez à jour la distance la plus courte entre les nœuds adjacents au nœud. Si la distance la plus courte mise à jour est inférieure à la distance précédente, mettez à jour la valeur dans le tableau des distances.
5) Enfin, obtenez le tableau distances, où distances[i] représente la distance la plus courte entre le nœud de départ et le nœud i.

Ce qui suit est un exemple de code pour implémenter l'algorithme de Dijkstra en utilisant 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. Algorithme de Bellman-Ford :
   L'algorithme de Bellman-Ford est un algorithme classique pour résoudre le problème du chemin le plus court, qui peut traiter des graphiques avec des bords de poids négatifs.

Les étapes de l'algorithme de Bellman-Ford sont les suivantes :
1) Définissez un tableau de distances, représentant la distance la plus courte entre le nœud de départ et les autres nœuds, et la valeur initiale est l'infini.
2) Définissez la distance la plus courte du nœud de départ sur 0.
3) Répétez les étapes suivantes jusqu'à ce que tous les bords soient détendus :
a) Tous les bords soient détendus, c'est-à-dire que la distance est raccourcie du bord suivant.
b) Mettez à jour le tableau des distances, et si un chemin plus court est trouvé, mettez à jour la distance la plus courte.
4) Enfin, vérifiez s'il existe une boucle de poids négatif. Si elle existe, cela signifie qu'il existe un chemin de poids négatif illimité dans le graphique.

Ce qui suit est un exemple de code utilisant PHP pour implémenter l'algorithme de 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;
}

Résumé :
Le problème du chemin le plus court des graphes est très courant dans les applications pratiques. En maîtrisant les deux algorithmes de Dijkstra et Bellman-Ford, nous. peut résoudre efficacement ce type de problème. Selon les caractéristiques et les exigences du graphique, le choix d'un algorithme approprié peut améliorer l'efficacité du calcul et améliorer les performances du programme. J'espère que l'introduction de cet article sera utile à tout le monde.

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!