Comment implémenter la recherche du chemin le plus court à l'aide de l'algorithme Floyd-Warshall en PHP

Dans le domaine de l'informatique, l'algorithme Floyd-Warshall (algorithme FW en abrégé) est un algorithme de programmation dynamique qui résout le problème du chemin le plus court pour toutes les paires de nœuds. Il peut résoudre des graphiques orientés ou non dans lesquels les poids de toutes les arêtes sont positifs ou négatifs, et présente des problèmes d'optimisation de complexité temporelle et spatiale.

En PHP, il existe de nombreuses façons d'implémenter l'algorithme FW, dont l'une consiste à utiliser un tableau bidimensionnel pour représenter la matrice d'adjacence du cœur. Voici les étapes spécifiques :

1. Construire la matrice de contiguïté

La matrice de contiguïté est un tableau bidimensionnel dans lequel chaque élément représente la distance entre deux sommets. S'il n'y a pas de connexion entre deux sommets, la valeur est l'infini. En PHP, la matrice de contiguïté peut être initialisée de la manière suivante :

// Initialize an empty adjacency matrix
$adjMatrix = [];

// Fill the adjacency matrix with infinite values
for($i=0; $i<$n; $i++) {
  for($j=0; $j<$n; $j++) {
    $adjMatrix[$i][$j] = INF;
  }
}

// Assign values to the adjacency matrix
for($i=0; $i<count($edges); $i++) {
  $source = $edges[$i][0];
  $dest = $edges[$i][1];
  $weight = $edges[$i][2];
  $adjMatrix[$source][$dest] = $weight;
}

où $n représente le nombre de nœuds dans l'ensemble du graphe et $edges représente le tableau de nombres d'arêtes, y compris le point de départ, le point final et le poids. de chaque bord.

2. Construire un tableau dp matriciel

Le tableau dp est également un tableau bidimensionnel, où chaque élément représente la longueur de chemin la plus courte du point de départ au point. Utilisez la matrice de contiguïté pour l'initialisation :

$dp = $adjMatrix;

3. Utilisez l'algorithme FW pour trouver le chemin le plus court

for($k=0; $k<$n; $k++) {
  for($i=0; $i<$n; $i++) {
    for($j=0; $j<$n; $j++) {
      if ($dp[$i][$j] > $dp[$i][$k] + $dp[$k][$j]) {
        $dp[$i][$j] = $dp[$i][$k] + $dp[$k][$j];
      }
    }
  }
}

où $k, $i, $j$ représentent respectivement les indices de ligne et de colonne dans la matrice de nœuds.

4. Résultats de sortie

for($i=0; $i<$n; $i++) {
  for($j=0; $j<$n; $j++) {
    if($dp[$i][$j] == INF) {
      echo "INF ";
    } else {
      echo $dp[$i][$j]." ";
    }
  }
  echo "
";
}

Ce qui précède est le processus d'utilisation de l'algorithme FW pour trouver le chemin le plus court en PHP. Il convient de noter que dans les applications pratiques, l’optimisation des algorithmes et le réglage des performances doivent être effectués en fonction de situations spécifiques pour répondre aux besoins réels.

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!