Algorithme Floyd-Warshall - Floyd–Warshall algorithm
Classer | Problème du plus court chemin toutes paires (pour les graphiques pondérés) |
---|---|
Structure de données | Graphique |
Performances dans le pire des cas | |
Le meilleur cas la performance | |
Performances moyennes | |
Complexité spatiale dans le pire des cas |
Algorithmes de recherche de graphiques et d' arbres |
---|
Annonces |
Rubriques connexes |
En informatique , le Floyd-Warshall algorithme (également connu comme l'algorithme de Floyd , l' algorithme Roy-Warshall , l' algorithme Roy-Floyd , ou l' algorithme de WFI ) est un algorithme de recherche des plus courts chemins dans une scène graphique pondéré avec un front positif ou négatif poids (mais sans cycles négatifs). Une seule exécution de l'algorithme trouvera les longueurs (poids additionnés) des chemins les plus courts entre toutes les paires de sommets. Bien qu'il ne renvoie pas les détails des chemins eux-mêmes, il est possible de reconstruire les chemins avec de simples modifications de l'algorithme. Des versions de l'algorithme peuvent également être utilisées pour trouver la fermeture transitive d'une relation ou (en relation avec le système de vote de Schulze ) les chemins les plus larges entre toutes les paires de sommets d'un graphe pondéré.
Histoire et dénomination
L'algorithme Floyd-Warshall est un exemple de programmation dynamique , et a été publié sous sa forme actuellement reconnue par Robert Floyd en 1962. Cependant, il est essentiellement le même que les algorithmes précédemment publiés par Bernard Roy en 1959 et aussi par Stephen Warshall en 1962 pour trouver la fermeture transitive d'un graphe, et est étroitement lié à l'algorithme de Kleene (publié en 1956) pour convertir un automate fini déterministe en une 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, également en 1962.
Algorithme
L'algorithme Floyd-Warshall compare tous les chemins possibles à travers le graphe entre chaque paire de sommets. Il est capable de le faire avec des comparaisons dans un graphe, même s'il peut y avoir jusqu'à arêtes dans le graphe, et chaque combinaison d'arêtes est testée. Il le fait en améliorant progressivement une estimation sur le chemin le plus court entre deux sommets, jusqu'à ce que l'estimation soit optimale.
Considérons un graphe avec des sommets numérotés de 1 à . Considérons en outre une fonction qui renvoie le chemin le plus court possible de à en utilisant uniquement les sommets de l'ensemble comme points intermédiaires le long du chemin. Maintenant, étant donné cette fonction, notre objectif est de trouver le chemin le plus court de chacun à chacun en utilisant n'importe quel sommet dans .
Pour chacune de ces paires de sommets, le pourrait être soit
- (1) un chemin qui ne passe pas (n'utilise que des sommets dans l'ensemble .)
ou
- (2) un chemin qui passe par (de à puis de à , les deux n'utilisant que des sommets intermédiaires dans )
Nous savons que le meilleur chemin de à qui n'utilise que les sommets à travers est défini par , et il est clair que s'il y avait un meilleur chemin de à à , alors la longueur de ce chemin serait la concaténation du plus court chemin de à (seulement en utilisant des sommets intermédiaires dans ) et le chemin le plus court de à (uniquement en utilisant des sommets intermédiaires dans ).
Si est le poids de l'arête entre les sommets et , nous pouvons définir en fonction de la formule récursive suivante : le cas de base est
et le cas récursif est
-
-
- .
-
Cette formule est au cœur de l'algorithme Floyd-Warshall. L'algorithme fonctionne en calculant d'abord toutes les paires pour , puis , et ainsi de suite. Ce processus se poursuit jusqu'à , et nous avons trouvé le chemin le plus court pour toutes les paires utilisant n'importe quel sommet intermédiaire. Le pseudocode de cette version de base est le suivant :
let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if
Exemple
L'algorithme ci-dessus est exécuté sur le graphique de gauche ci-dessous :
Avant la première récursivité de la boucle externe, étiquetée k = 0 ci-dessus, les seuls chemins connus correspondent aux arêtes uniques du graphe. A k = 1 , les chemins qui passent par le sommet 1 sont trouvés : en particulier, le chemin [2,1,3] est trouvé, remplaçant le chemin [2,3] qui a moins d'arêtes mais est plus long (en termes de poids ). A k = 2 , les chemins passant par les sommets {1,2} sont trouvés. Les cases rouges et bleues montrent comment le chemin [4,2,1,3] est assemblé à partir des deux chemins connus [4,2] et [2,1,3] rencontrés dans les itérations précédentes, avec 2 à l'intersection. Le chemin [4,2,3] n'est pas considéré, car [2,1,3] est le plus court chemin rencontré jusqu'à présent de 2 à 3. A k = 3 , chemins passant par les sommets {1,2,3} sont trouvés. Enfin, à k = 4 , tous les chemins les plus courts sont trouvés.
La matrice de distance à chaque itération de k , avec les distances mises à jour en gras , sera :
k = 0 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
je | 1 | 0 | ?? | -2 | ?? |
2 | 4 | 0 | 3 | ?? | |
3 | ?? | ?? | 0 | 2 | |
4 | ?? | -1 | ?? | 0 |
k = 1 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
je | 1 | 0 | ?? | -2 | ?? |
2 | 4 | 0 | 2 | ?? | |
3 | ?? | ?? | 0 | 2 | |
4 | ?? | -1 | ?? | 0 |
k = 2 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
je | 1 | 0 | ?? | -2 | ?? |
2 | 4 | 0 | 2 | ?? | |
3 | ?? | ?? | 0 | 2 | |
4 | 3 | -1 | 1 | 0 |
k = 3 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
je | 1 | 0 | ?? | -2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | ?? | ?? | 0 | 2 | |
4 | 3 | -1 | 1 | 0 |
k = 4 | j | ||||
1 | 2 | 3 | 4 | ||
---|---|---|---|---|---|
je | 1 | 0 | -1 | -2 | 0 |
2 | 4 | 0 | 2 | 4 | |
3 | 5 | 1 | 0 | 2 | |
4 | 3 | -1 | 1 | 0 |
Comportement avec des cycles négatifs
Un cycle négatif est un cycle dont la somme des arêtes donne une valeur négative. Il n'y a pas de chemin le plus court entre une paire de sommets , qui font partie d'un cycle négatif, car les longueurs de chemin de à peuvent être arbitrairement petites (négatives). Pour une sortie numériquement significative, l'algorithme Floyd-Warshall suppose qu'il n'y a pas de cycles négatifs. Néanmoins, s'il y a des cycles négatifs, l'algorithme de Floyd-Warshall peut être utilisé pour les détecter. L'intuition est la suivante :
- L'algorithme Floyd-Warshall révise de manière itérative les longueurs de chemin entre toutes les paires de sommets , y compris où ;
- Initialement, la longueur du chemin est nulle ;
- Un chemin ne peut l'améliorer que s'il a une longueur inférieure à zéro, c'est-à-dire qu'il dénote un cycle négatif ;
- Ainsi, après l'algorithme, sera négatif s'il existe un chemin de longueur négative de retour à .
Par conséquent, pour détecter les cycles négatifs à l'aide de l'algorithme Floyd-Warshall, on peut inspecter la diagonale de la matrice de chemin, et la présence d'un nombre négatif indique que le graphique contient au moins un cycle négatif. Pendant l'exécution de l'algorithme, s'il y a un cycle négatif, des nombres exponentiellement grands peuvent apparaître, aussi grands que , où est la plus grande valeur absolue d'un front négatif dans le graphe. Pour éviter les problèmes de débordement/sous-débordement, il convient de vérifier les nombres négatifs sur la diagonale de la matrice de chemin dans la boucle for interne de l'algorithme. Évidemment, dans un graphe non orienté, une arête négative crée un cycle négatif (c'est-à-dire une marche fermée) impliquant ses sommets incidents. En considérant toutes les arêtes de l' exemple de graphique ci - dessus comme non orientées, par exemple la séquence de sommets 4 – 2 – 4 est un cycle avec une somme de poids −2.
Reconstitution du chemin
L'algorithme Floyd-Warshall ne fournit généralement que les longueurs des chemins entre toutes les paires de sommets. Avec de simples modifications, il est possible de créer une méthode pour reconstruire le chemin réel entre deux sommets d'extrémité. Bien que l'on puisse être enclin à stocker le chemin réel de chaque sommet à chaque autre sommet, cela n'est pas nécessaire, et en fait, est très coûteux en termes de mémoire. Au lieu de cela, l' arbre du chemin le plus court peut être calculé pour chaque nœud dans le temps en utilisant la mémoire pour stocker chaque arbre, ce qui nous permet de reconstruire efficacement un chemin à partir de deux sommets connectés.
Pseudocode
let dist be a array of minimum distances initialized to (infinity) let next be a array of vertex indices initialized to null procedure FloydWarshallWithPathReconstruction() is for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) next[u][v] ← v for each vertex v do dist[v][v] ← 0 next[v][v] ← v for k from 1 to |V| do // standard Floyd-Warshall implementation for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] then dist[i][j] ← dist[i][k] + dist[k][j] next[i][j] ← next[i][k]
procedure Path(u, v) if next[u][v] = null then return [] path = [u] while u ≠ v u ← next[u][v] path.append(u) return path
Une analyse
Laissez - être , le nombre de sommets. Pour trouver tous de (pour tous et ) à partir de ceux de nécessite des opérations. Puisque nous commençons et calculons la séquence de matrices , , , , le nombre total d'opérations utilisées est . Par conséquent, la complexité de l'algorithme est .
Applications et généralisations
L'algorithme Floyd-Warshall peut être utilisé pour résoudre les problèmes suivants, entre autres :
- Chemins les plus courts dans les graphes orientés (algorithme de Floyd).
- Fermeture transitive de graphes orientés (algorithme de Warshall). Dans la formulation originale de l'algorithme de Warshall, le graphique est non pondéré et représenté par une matrice d'adjacence booléenne . Ensuite, l'opération d'addition est remplacée par la conjonction logique (ET) et l'opération minimale par la disjonction logique (OU).
- Trouver une expression régulière désignant le langage régulier accepté par un automate fini ( algorithme de Kleene , une généralisation étroitement liée de l'algorithme Floyd-Warshall)
- Inversion de matrices réelles ( algorithme de Gauss-Jordan )
- Routage optimal. Dans cette application, on s'intéresse à trouver le chemin avec le flux maximum entre deux sommets. Cela signifie que, plutôt que de prendre des minima comme dans le pseudocode ci-dessus, on prend plutôt des maxima. Les poids de bord représentent des contraintes fixes sur le flux. Les poids de chemin représentent des goulots d'étranglement ; ainsi l'opération d'addition ci-dessus est remplacée par l'opération minimale.
- Calcul rapide des réseaux Pathfinder .
- Chemins les plus larges/chemins de bande passante maximale
- Calcul de la forme canonique des matrices différentielles (DBM)
- Calculer la similarité entre des graphiques
- Fermeture transitive dans les graphes ET/OU/seuil.
Implémentations
Des implémentations sont disponibles pour de nombreux langages de programmation .
- Pour C++ , dans la bibliothèque boost::graph
- Pour C# , chez QuickGraph
- Pour C# , à QuickGraphPCL (Un fork de QuickGraph avec une meilleure compatibilité avec les projets utilisant des bibliothèques de classes portables.)
- Pour Java , dans la bibliothèque Apache Commons Graph
- Pour JavaScript , dans la bibliothèque Cytoscape
- Pour MATLAB , dans le package Matlab_bgl
- Pour Perl , dans le module Graph
- Pour Python , dans la bibliothèque SciPy (module scipy.sparse.csgraph ) ou la bibliothèque NetworkX
- Pour R , en colis e1071 et Rfast
Comparaison avec d'autres algorithmes du plus court chemin
L'algorithme Floyd-Warshall est un bon choix pour calculer les chemins entre toutes les paires de sommets dans les graphes denses , dans lesquels la plupart ou toutes les paires de sommets sont connectées par des arêtes. Pour les graphes clairsemés avec des poids de bord non négatifs, une complexité asymptotique inférieure peut être obtenue en exécutant l'algorithme de Dijkstra à partir de chaque sommet de départ possible, car le pire des cas d'exécution de Dijkstra répété (en utilisant des tas de Fibonacci ) est plus petit que le temps d'exécution du Floyd –Algorithme de Warshall quand est significativement plus petit que . Pour les graphes clairsemés avec des bords négatifs mais pas de cycles négatifs, l'algorithme de Johnson peut être utilisé, avec le même temps d'exécution asymptotique que l'approche répétée de Dijkstra.
Il existe également des algorithmes connus utilisant la multiplication matricielle rapide pour accélérer le calcul du chemin le plus court de toutes les paires dans les graphiques denses, mais ceux-ci font généralement des hypothèses supplémentaires sur les poids des bords (comme exiger qu'ils soient de petits entiers). De plus, en raison des facteurs constants élevés dans leur temps d'exécution, ils ne fourniraient une accélération par rapport à l'algorithme Floyd-Warshall que pour les très grands graphiques.