Algorithme Floyd-Warshall - Floyd–Warshall algorithm

Algorithme Floyd-Warshall
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

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 :

Floyd-Warshall example.svg

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 uv
        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 :

Implémentations

Des implémentations sont disponibles pour de nombreux langages de programmation .

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.

Les références

Liens externes