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

WBOY
Libérer: 2023-06-25 21:22:01
original
1576 Les gens l'ont consulté

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;
}
Copier après la connexion

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.

  1. 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;
Copier après la connexion
  1. 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];
      }
    }
  }
}
Copier après la connexion

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

  1. 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 "
";
}
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!