Quel est le principe de l’algorithme de Floyd ?

Le principe de l'algorithme de Floyd est un algorithme qui utilise l'idée de programmation dynamique pour trouver le chemin le plus court entre plusieurs points sources dans un graphe pondéré donné. Il est similaire à l'algorithme de Dijkstra. algorithme qui utilise l'idée de programmation dynamique pour trouver le chemin le plus court entre plusieurs points sources dans un graphe pondéré donné. Algorithme pour trouver le chemin le plus court dans un graphe pondéré.

Floyd算法 Également connue sous le nom de méthode d'interpolation, c'est une méthode qui utilise l'idée de programmation dynamique pour trouver le chemin le plus court entre plusieurs points sources dans un graphe pondéré donné L'algorithme est similaire à l'algorithme de Dijkstra. L'algorithme porte le nom de Robert Floyd, l'un des fondateurs, lauréat du Turing Award 1978 et professeur d'informatique à l'Université de Stanford

En informatique, l'algorithme Floyd-Warshall est une méthode avec algorithme pour trouver chemins les plus courts dans les graphiques pondérés avec des poids de bord positifs ou négatifs (mais pas de périodes négatives). Une seule exécution de l'algorithme trouvera la longueur (pondérée) du chemin le plus court entre toutes les paires de sommets. Bien qu'il ne renvoie pas les détails du chemin lui-même, le chemin peut être reconstruit avec de simples modifications de l'algorithme. Des versions de cet algorithme peuvent également être utilisées pour trouver la fermeture transitive d'une relation R, ou (lié au système de vote Schulze) le chemin le plus large entre toutes les paires de sommets dans un graphe pondéré.

L'algorithme Floyd-Warshall est un exemple de programmation dynamique et a été publié sous sa forme actuellement acceptée par Robert Floyd en 1962. Cependant, il s'agit essentiellement du même algorithme pour trouver des fermetures transitives de graphes publié précédemment par Bernard Roy en 1959 et Stephen Warshall en 1962, et est étroitement lié à l'algorithme de Kleene en 1956) pour convertir des automates finis déterministes Convertir en expression régulière. La formulation moderne de l’algorithme sous forme de trois boucles for imbriquées a été décrite pour la première fois par Peter Ingerman en 1962.

Cet algorithme est également connu sous le nom d'algorithme de Floyd, d'algorithme de Roy-Warshall, d'algorithme de Roy-Floyd ou d'algorithme WFI.

Édition de l'idée de base

1. Matrice de chemin

Trouver tous les deux de la matrice de poids d'un graphique Matrice de chemin le plus court entre les points .

À partir de la matrice de contiguïté pondérée A=[a(i,j)] n×n du graphe, mettez-la à jour de manière récursive n fois, c'est-à-dire construisez-la à partir de la matrice D(0)=A selon à une formule La matrice D(1) est obtenue ; et la même formule est utilisée pour construire D(2) à partir de D(1 ... enfin, la matrice D(n) est construite à partir de D(n-1) ; ) en utilisant la même formule. Les éléments de la ligne i et de la colonne j de la matrice D(n) sont la longueur de chemin la plus courte du sommet i au sommet D(n) est appelée la matrice de distance du graphique. En même temps, un chemin de matrice de nœuds successeur peut. également être introduit pour enregistrer la distance entre deux points le chemin le plus court.

Utilisez la technologie de relaxation (opération de relaxation) pour détendre tous les autres points entre i et j. La complexité temporelle est donc O(n^3);

2 L'équation de transition d'état

L'équation de transition d'état est la suivante : map[i,j] :=min {map[i,k]+map[k,j],map[i,j]};

map[i,j] représente la distance la plus courte de i à j, K est le exhaustif i,j Le point d'arrêt, la valeur initiale de map[n,n] doit être 0, ou faire ce que signifie la question.

Bien sûr, si cette route n'est pas accessible, un traitement particulier doit être fait, par exemple, il n'y a pas de carte[i,k] route.

Éditeur de processus d'algorithme

1, à partir de n'importe quel chemin unilatéral. La distance entre les deux points est le poids de l’arête. S’il n’y a pas d’arête reliant les deux points, le poids est infini.

2. Pour chaque paire de sommets u et v, voyez s'il existe un sommet w tel que le chemin de u à w à v est plus court que le chemin connu. Si c'est le cas, mettez-le à jour.

Représente le graphe comme une matrice de contiguïté G. S'il existe un chemin de Vi à Vj, alors G[i][j]=d, d représente la longueur du chemin ; j ] = infini. Définissez une matrice D pour enregistrer les informations du point inséré D[i][j] représente le point qui doit être passé de Vi à Vj. Initialisez D[i][j]=j. Insérez chaque sommet dans le graphique et comparez la distance après l'insertion avec la distance d'origine, G[i][j] = min( G[i][j], G[i][k]+G[k][j ] ), si la valeur de G[i][j] devient plus petite, alors D[i][j]=k. G contient les informations du chemin le plus court entre deux points, tandis que D contient les informations du chemin le plus court.

Par exemple, vous souhaitez trouver le chemin de la V5 à la V1. D'après D, si D(5,1)=3, cela signifie que le chemin de V5 à V1 passe par V3 est {V5,V3,V1}. Si D(5,3)=3, cela signifie que V5 et. V3 sont directement connectés. Si D (3,1) = 1, indiquant que V3 et V1 sont directement connectés.

Complexité temporelle et édition de la complexité spatiale

Complexité temporelle : O(n^3) ;

Complexité spatiale : O(n ^2)

Analyse et édition des avantages et des inconvénients

L'algorithme Floyd convient à l'APSP (All Pairs Shortest Paths, multi-source shortest path), qui est un algorithme de programmation dynamique, dense Le graphique a le meilleur effet et les poids des bords peuvent être positifs ou négatifs. Cet algorithme est simple et efficace. En raison de la structure compacte à triple boucle, pour les graphes denses, l'efficacité est supérieure à l'exécution de |V| fois de l'algorithme de Dijkstra et supérieure à l'exécution de |V| de l'algorithme SPFA.

Avantages : facile à comprendre, peut calculer la distance la plus courte entre deux nœuds quelconques et le code est simple à écrire.

Inconvénients : La complexité temporelle est relativement élevée et elle n'est pas adaptée au calcul de grandes quantités de données.

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!