Floyd Warshall Algorithm

MoyenPlus courts chemins Programmation dynamique

+10

Un graphe orienté comportant n nœuds, numérotés de 0 à n-1, est donné sous la forme d’une matrice n par n : matrix[i][j] est le poids de l’arête allant du nœud i au nœud j, ou -1 s’il n’y en a pas, et matrix[i][i] vaut 0. La longueur d’un chemin est la somme des poids de ses arêtes.

Renvoyez une matrice n par n dont l’entrée [i][j] est la longueur du plus court chemin du nœud i au nœud j, ou -1 si le nœud j ne peut pas être atteint depuis le nœud i.

Fonction

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: les poids des arêtes : matrix[i][j] est le poids de l’arête de i à j, ou -1 lorsqu’il n’y en a pas
Renvoieinteger-2d-array: la distance la plus courte pour chaque paire de nœuds, -1 lorsqu'il n'y a pas de chemin

Contraintes

1 ≤ n ≤ 100, où n = matrix.length = matrix[i].length
matrix[i][i] = 0
Pour i ≠ j, matrix[i][j] vaut -1 (aucune arête) ou 0 ≤ matrix[i][j] ≤ 1000.
Les arêtes sont à sens unique : matrix[i][j] et matrix[j][i] sont indépendantes.

Exemples

Entrée: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Sortie: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Explication: En passant par le nœud 1, le nœud 0 atteint le nœud 2 en 6 au lieu de 11, et le nœud 3 en 9. Le nœud 1 atteint le nœud 0 en passant par le nœud 2 en 3. Rien ne part du nœud 3, donc sa ligne vaut -1 hors de la diagonale.

Entrée: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Sortie: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Explication: L’arête de 2 à 1 a un poids de 0, donc 0 → 2 → 1 coûte 1, ce qui est inférieur au coût direct de 6. Aucune arête ne part du nœud 1 ni n’entre dans le nœud 0 ; ces paires restent donc à -1.

Pour aller plus loin

Après avoir construit le tableau, le coût d’une arête diminue. Peux-tu mettre à jour chaque distance en O(n²) au lieu de relancer les boucles O(n³) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Tu as besoin du plus court chemin pour chaque paire de sommets. Floyd-Warshall trouve les n² réponses avec une seule triple boucle. À chaque étape, les chemins peuvent passer par un sommet supplémentaire, au prix d’une comparaison par paire : le meilleur chemin trouvé jusque-là face au chemin passant par le nouveau sommet.

Prolongez chaque chemin d'une arête jusqu'à ce que rien ne change

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Partez de la matrice et, à chaque passage, prolongez chaque itinéraire d’une arête : un itinéraire de i à m plus l’arête m → j constitue un itinéraire de i à j, conservé s’il est plus court. Répétez jusqu’à ce qu’un passage ne change rien.

Après p passages, tous les itinéraires les plus courts comportant jusqu’à p+1 arêtes sont trouvés. Aucun poids n’est négatif, donc il existe un itinéraire le plus court sans boucle et comportant au plus n-1 arêtes, et les passages s’arrêtent lorsque toutes les distances sont définitives. Un passage représente n³ = 10^6 étapes pour 100 nœuds, et une longue chaîne d’itinéraires les plus courts nécessite jusqu’à n passages : O(n⁴), soit jusqu’à 10^8 étapes.

Algorithme

Copiez matrix dans dist.
Pour chaque i, m et j : si dist[i][m] et matrix[m][j] existent tous les deux, calculez leur somme.
Si dist[i][j] vaut -1 ou est supérieur à la somme, stockez la somme et notez que le passage a modifié quelque chose.
Répétez le passage jusqu'à ce qu'il ne modifie plus rien, puis renvoyez dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Floyd-Warshall : autoriser un arrêt supplémentaire à chaque tour

Intuition

Limitez les nœuds où un trajet peut s’arrêter entre ses extrémités. La table commence comme la matrice, avec les trajets sans arrêt. Après le tour k, dist[i][j] est le trajet le plus court dont tous les arrêts se trouvent parmi les nœuds 0 à k, et le dernier tour donne la réponse.

Au tour k, le meilleur trajet qui peut aussi s’arrêter à k soit évite k, et la table le contient déjà, soit passe une fois par k, puisqu’aucun poids n’est négatif. Ses deux moitiés ne s’arrêtent qu’aux nœuds 0 à k-1, donc elles correspondent à dist[i][k] et dist[k][j].

Dans le premier exemple, le tour 1 remplace le trajet direct de 11 entre le nœud 0 et le nœud 2 par 6. Le tour 2 donne une distance de 6 + 3 = 9 entre le nœud 0 et le nœud 3, avec l’arrêt au nœud 1 à l’intérieur du trajet de 6.

Une seule table suffit : la ligne k et la colonne k ne changent pas au tour k, car dist[k][k] vaut 0.

Algorithme

Copiez matrix dans dist ; -1 signifie qu’aucun itinéraire n’a encore été trouvé.
Pour k de 0 à n-1, et pour chaque i et j : ignorez la paire si dist[i][k] ou dist[k][j] vaut -1.
Sinon, calculez via = dist[i][k] + dist[k][j].
Si dist[i][j] vaut -1 ou est supérieur à via, définissez-le sur via.
Renvoyez dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Pièges et cas limites

Ajouter -1 comme s’il s’agissait d’un poids : -1 + 5 = 4 ressemble à un trajet. Vérifie d’abord les deux parties et considère un -1 dans dist[i][j] comme pire que n’importe quel trajet.
Placer la boucle sur k à l’intérieur. Les trajets passant par les arrêts de 0 à k-1 doivent être définitifs avant que le nœud k soit pris en compte.
Utiliser le plus grand entier comme valeur d’infini : en additionner deux provoque un dépassement de capacité d’un entier 32 bits et donne une distance négative. Une distance réelle est au plus égale à 99 × 1000 = 99,000, donc 10^9 est sûr, car 2 × 10^9 est inférieur à 2^31-1.
Supposer que les arêtes vont dans les deux sens. Dans le deuxième exemple, le nœud 0 atteint le nœud 1, mais le nœud 1 n’atteint aucun nœud.
Exécuter une recherche en largeur, qui ignore les poids : dans le premier exemple, elle indique 11 entre le nœud 0 et le nœud 2, et non 6.

Questions fréquentes3

Quelle est la complexité temporelle de l’algorithme de Floyd Warshall ?

Un temps de O(n³) pour n nœuds : trois boucles imbriquées sur les nœuds, avec une addition et une comparaison par étape, 10^6 étapes pour 100 nœuds. L’espace requis est de O(n²) pour le tableau des distances, qui peut être mis à jour sur place.

Floyd Warshall fonctionne-t-il avec des poids d’arête négatifs ?

Oui, tant qu’il n’y a pas de cycle négatif, c’est-à-dire une boucle dont la somme des poids est inférieure à 0. En présence d’un cycle négatif, les plus courts chemins ne sont pas définis, et le tableau le montre : certains dist[i][i] se retrouvent inférieurs à 0.

Quand faut-il utiliser Floyd Warshall plutôt que l’algorithme de Dijkstra ?

Utilisez Floyd-Warshall pour chaque paire de nœuds dans un graphe dense comptant jusqu’à quelques centaines de nœuds. Dijkstra exécuté depuis chaque nœud coûte O(n³) avec un tableau et O(n · E log n) avec un tas, ce qui est avantageux dans les grands graphes creux. Floyd-Warshall ne nécessite pas de tas et accepte les arêtes négatives, contrairement à Dijkstra.

def shortestDistances(matrix):
    # Écrivez le code ici

Test #1

Test #2

Argument

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Résultat attendu

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]