Des plus court chemins entre toute paire de sommets par l’algorithme de Floyd-Warshall

L’algorithme de Floyd-Warshall (parfois nommé Roy-Floyd ou Roy-Warshall) est un algorithme permettant de calculer l’ensemble des plus courts chemins entre toute paire de sommets dans un graphe donné. Ce problème est souvent dénoté (*-to-*) (se prononce “star-to-star”).

L’algorithme de Floyd-Warshall

Principe

L’algorithme de Floyd-Warshall consiste à calculer inductivement l’ensemble des chemins les plus courts entre tout couple de sommets dans un graphe en n’empruntant qu’un sous-ensemble E des sommets comme sommets intermédiaires.

En faisant croître E jusqu’à couvrir l’ensemble des sommets du graphe, on obtient alors l’ensemble des chemins les plus courts.

Algorithme

Ici, distances est une matrice dont la coordonnée (i, j) contient au final la longueur du plus court chemin reliant i à j. Elle est initialisée partout à l’infini sauf sur sa diagonale où elle vaut 0 et dans les cases (i, j) où i est relié à j dans le graphe auquel cas elle vaut le poids de l’arête reliant i à j.

Dans cet exemple, le graphe utilisé est le suivant (représenté sous forme d’un tableau de paires (voisin, poids)) :

01234517311252

Routage

Pour récupérer des plus courts chemins, il est nécessaire de retenir, à chaque fois que la matrice des distances est mise à jour, par quel sommet intermédiaire le chemin le plus court trouvé est passé.

Le code devient :

Avec le graphe ci-dessus, on obtient les matrices résultats suivantes (à gauche la matrice de distances, à droite celle des prédécesseurs) :

0 1 2 4 6 2
1 0 1 3 5 1
2 1 0 4 6 2
4 3 4 0 2 2
6 5 6 2 0 4
2 1 2 2 4 0
x 0 1 5 3 1
1 x 1 5 3 1
1 2 x 5 3 1
1 5 1 x 3 3
1 5 1 4 x 3
1 5 1 5 3 x

Pour retrouver un chemin d’un sommet i à un sommet j, il faut alors récursivement chercher sur la ligne i les sommets prédécesseurs de j jusqu’à finalement revenir i.

Cherchons par exemple un plus court chemin du sommet 2 au sommet 4. La matrice de distances nous dit que la longueur du chemin recherché est de 6.

On a routes[2][4] = 3. Cela signifie que le prédécesseur direct du noeud 4 sur un plus court chemin allant de 2 à 4 est 3.

Cherchons à présent un plus court chemin allant de 2 à 3. Cette information est donnée par routes[2][3] = 5. Il faut donc se rendre en 5.

En continuant ainsi, on obtient que le prédécesseur de 5 est 1 (routes[2][5] = 1), puis que le prédécesseur de 1 est 2, notre sommet initial. On obtient donc le chemin 2 – 1 – 5 – 3 – 4, de longueur 1 + 1 + 2 + 2 = 6.

Complexité

Dans le cadre général, l’algorithme de Floyd-Warshall a clairement une complexité en O(|V|3).

En pratique, il est souvent possible d’exploiter la structure spécifique du graphe que l’on considère (par exemple sa symétrie) pour réduire cette complexité.

Exemple

Considérons à nouveau le graphe suivant, et construisons ensemble ses matrices de distances (à gauche) et de prédécesseurs (à droite) :

01234517311252

Les matrices sont initialisées comme suit :

0 1 7 3
1 0 1 1
7 1 0
0 2 2
2 0 5
3 1 2 5 0
x 0 0 x x 0
1 x 1 x x 1
2 2 x x x x
x x x x 3 3
x x x 4 x 4
5 5 x 5 5 x

On commence la première boucle avec k = 0. Pour tout couple (i, j), il nous faut lire dans la matrice des distances si aller de i à k puis de k à j est plus court que d’aller directement de i à j.

On se rend compte que le chemin 2 – 5 n’est plus de longueur infinie car le sommet 0 peut relier les sommets 2 et 5 :

0 1 7 3
1 0 1 1
7 1 0 10
0 2 2
2 0 5
3 1 10 2 5 0
x 0 0 x x 0
1 x 1 x x 1
2 2 x x x 0
x x x x 3 3
x x x 4 x 4
5 5 0 5 5 x

Continuons avec k = 1. On autorise à présent l’insertion du sommet 1 dans les plus courts chemins actuellement connus. Notez ici que l’ajout de 1 ne crée pas de nouveaux chemins (remplacement de “x” dans la matrice), mais qu’il réduit considérablement la longueur de chemins existants :

0 1 2 2
1 0 1 1
2 1 0 2
0 2 2
2 0 5
2 1 2 2 5 0
x 0 1 x x 1
1 x 1 x x 1
1 2 x x x 1
x x x x 3 3
x x x 4 x 4
1 5 1 5 5 x

Autorisons à présent l’utilisation du sommet k = 2. Cela n’apporte aucune modification aux matrices :

0 1 2 2
1 0 1 1
2 1 0 2
0 2 2
2 0 5
2 1 2 2 5 0
x 0 1 x x 1
1 x 1 x x 1
1 2 x x x 1
x x x x 3 3
x x x 4 x 4
1 5 1 5 5 x

Passons à k = 3. On voit bien sur le graphe que 5 – 3 – 4 est plus court que l’actuel 5 – 4. Cette modification sera apportée aux matrices par l’autorisation de l’ajout du sommet 3 :

0 1 2 2
1 0 1 1
2 1 0 2
0 2 2
2 0 4
2 1 2 2 4 0
x 0 1 x x 1
1 x 1 x x 1
1 2 x x x 1
x x x x 3 3
x x x 4 x 3
1 5 1 5 3 x

La variable k prend à présent la valeur 4. Toutefois, ajouter 4 aux chemins existants ne les raccourcit pas :

0 1 2 2
1 0 1 1
2 1 0 2
0 2 2
2 0 4
2 1 2 2 4 0
x 0 1 x x 1
1 x 1 x x 1
1 2 x x x 1
x x x x 3 3
x x x 4 x 3
1 5 1 5 3 x

Enfin, on arrive à k = 5. Le noeud associé ayant une place relativement centrale dans notre exemple, de nombreuses modifications vont être apportées, car il deviendra par exemple possible de relier 0 à 4 en “branchant” le plus court chemin de 0 à 5 à celui de 5 à 4 (c’est à dire que le prédécesseur de 4 sur le plus court chemin de 0 à 4 deviendra le prédécesseur de 4 sur le plus court chemin de 5 à 4, soit 3) :

0 1 2 4 6 2
1 0 1 3 5 1
2 1 0 4 6 2
4 3 4 0 2 2
6 5 6 2 0 4
2 1 2 2 4 0
x 0 1 5 3 1
1 x 1 5 3 1
1 2 x 5 3 1
1 5 1 x 3 3
1 5 1 4 x 3
1 5 1 5 3 x

Terminaison

L’algorithme de Floyd-Warshall termine clairement car il ne contient que des boucles finies dont les conditions d’arrêt ne dépendent pas des calculs internes.

Correction

Pour prouver la correction de cet algorithme, nous allons procéder par induction.

Plus exactement, nous allons montrer que, à la fin de la première boucle pour la valeur k, nous avons la propriété “la matrice des distances contient l’ensemble des longueurs des chemins les plus courts n’empruntant que des sommets intermédiaires entre 1 et k“.

Cette propriété est vraie pour l’état initial, car aucun sommet intermédiaire n’est autorisé, et la matrice est initialisée avec les arêtes du graphe.

Supposons la propriété vraie pour k. On remarque que le chemin le plus court entre i et j passant par des sommets entre 0 et k+1 est sous l’une de ces deux formes :

  • Il ne passe pas par k+1. La distance étant minimale par hypothèse d’induction, elle reste minimale.
  • Il passe par k+1. Dans ce cas, le chemin reliant i à k+1 ne passe que par des sommets entre 0 et k, et il en va de même pour le chemin entre k+1 et j. La distance devient d(i, k+1) + d(k+1, j), qui est minimale.
Publié le

Commentaires (1)

Laisser un commentaire