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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
# This function returns a matrix of NxN integers # They correspond to the lengths of the shortest paths between every pair of nodes def floydWarshall (graph) : # Distances is the result of the algorithm # It is initialized with infinite values where we do not have information # The diagonal is initialized to 0, and the graph edges to their values distances = [[float("inf") for i in range(len(graph))] for i in range(len(graph))] for node in range(len(graph)) : distances[node][node] = 0 for neighbor, weight in graph[node] : distances[node][neighbor] = weight # For every new node to include in the paths for k in range(len(graph)) : # For every pair of nodes for i in range(len(graph)) : for j in range(len(graph)) : # We check if it is shorter to go through the new node at some point in the paths # When it is the case, we update the distance potentialNewDistance = distances[i][k] + distances[k][j] if potentialNewDistance < distances[i][j] : distances[i][j] = potentialNewDistance # We return the filled matrix of distances return distances ################################################################### # Test graph graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]] result = floydWarshall(graph) print(repr(result)) |
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)) :
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 :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
# This function returns a matrix of NxN integers # They correspond to the lengths of the shortest paths between every pair of nodes def floydWarshall (graph) : # Distances is the result of the algorithm # It is initialized with infinite values where we do not have information # The diagonal is initialized to 0, and the graph edges to their values distances = [[float("inf") for i in range(len(graph))] for i in range(len(graph))] predecessors = [[None for i in range(len(graph))] for i in range(len(graph))] # <-- new code (we keep track of the predecessors of every node along the shortest paths) for node in range(len(graph)) : distances[node][node] = 0 for neighbor, weight in graph[node] : distances[node][neighbor] = weight predecessors[node][neighbor] = node # <-- new code (we initialize the predecessors using the direct edges) # For every new node to include in the paths for k in range(len(graph)) : # For every pair of nodes for i in range(len(graph)) : for j in range(len(graph)) : # We check if it is shorter to go through the new node at some point in the paths # When it is the case, we update the distance potentialNewDistance = distances[i][k] + distances[k][j] if potentialNewDistance < distances[i][j] : distances[i][j] = potentialNewDistance predecessors[i][j] = predecessors[k][j] # <-- new code (when we update the distance, we keep track of the associated route) # We return the filled matrix of distances and predecessors return (distances, predecessors) # <-- new code (we also return the routes) ################################################################### # Test graph graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]] (result, routes) = floydWarshall(graph) print(repr(result)) print(repr(routes)) |
Avec le graphe ci-dessus, on obtient les matrices résultats suivantes (à gauche la matrice de distances, à droite celle des prédécesseurs) :
|
|
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) :
Les matrices sont initialisées comme suit :
|
|
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 :
|
|
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 :
|
|
Autorisons à présent l’utilisation du sommet k = 2. Cela n’apporte aucune modification aux matrices :
|
|
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 :
|
|
La variable k prend à présent la valeur 4. Toutefois, ajouter 4 aux chemins existants ne les raccourcit pas :
|
|
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) :
|
|
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.
Pourquoi lors du routage on a
predecessors[i][j]=predecessors[k][j]
et non pas
predecessors[i][j]=k ?