algorithm
Algorithme Floyd-Warshall

Algorithme du chemin le plus court de toutes les paires

L'algorithme de Floyd-Warshall permet de trouver les chemins les plus courts dans un graphique pondéré avec des poids de bord positifs ou négatifs. Une seule exécution de l'algorithme trouvera les longueurs (poids additionnés) des plus courts chemins entre toutes les paires de sommets. Avec une petite variation, il peut imprimer le chemin le plus court et détecter les cycles négatifs dans un graphique. Floyd-Warshall est un algorithme de programmation dynamique.

Regardons un exemple. Nous allons appliquer l'algorithme de Floyd-Warshall sur ce graphique:

La première chose à faire est de prendre deux matrices 2D. Ce sont des matrices d'adjacence . La taille des matrices va être le nombre total de sommets. Pour notre graphique, nous prendrons 4 * 4 matrices. La distance Matrix va stocker la distance minimale trouvée entre deux sommets. Au début, pour les arêtes, s'il y a un bord entre uv et la distance / poids est w , nous allons stocker: distance[u][v] = w . Pour tous les bords qui n'existent pas, nous allons mettre l' infini . La matrice de chemin sert à régénérer le chemin de distance minimum entre deux sommets. Donc, au départ, s'il y a un chemin entre u et v , nous allons mettre le path[u][v] = u . Cela signifie que la meilleure façon d’arriver à vertex-v à partir de vertex-u est d’utiliser l’arête qui connecte v avec u . S'il n'y a pas de chemin entre deux sommets, nous allons y mettre N indiquant qu'il n'y a pas de chemin disponible maintenant. Les deux tableaux de notre graphique ressembleront à:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  6  |  15 |            |  1  |  N  |  1  |  1  |  1  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  | inf |  0  | -2  | inf |            |  2  |  N  |  N  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  | inf | inf |  0  |  2  |            |  3  |  N  |  N  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  | inf | inf |  0  |            |  4  |  4  |  N  |  N  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

Comme il n'y a pas de boucle, les diagonales sont définies sur N. Et la distance du sommet lui-même est 0 .

Pour appliquer l'algorithme de Floyd-Warshall, nous allons sélectionner un sommet médian k . Ensuite, pour chaque sommet i , nous allons vérifier si nous pouvons aller de i à k , puis de k à j , où j est un autre sommet et minimiser le coût de passer de i à j . Si la distance actuelle [i] [j] est supérieure à la distance [i] [k] + distance [k] [j] , nous allons mettre la distance [i] [j] égale à la somme de ces deux distances . Et le chemin [i] [j] sera mis au chemin [k] [j] , car il vaut mieux aller de i à k , puis k à j . Tous les sommets seront sélectionnés comme k . Nous aurons 3 boucles imbriquées: pour k allant de 1 à 4, je passe de 1 à 4 et j va de 1 à 4. Nous allons vérifier:

if distance[i][j] > distance[i][k] + distance[k][j]
    distance[i][j] := distance[i][k] + distance[k][j]
    path[i][j] := path[k][j]
end if

Donc, ce que nous vérifions en fait, c'est que pour chaque paire de sommets, la distance est-elle plus courte en passant par un autre sommet? Le nombre total d'opérations pour notre graphique sera 4 * 4 * 4 = 64 . Cela signifie que nous allons faire cette vérification 64 fois. Regardons quelques-unes d'entre elles:

Lorsque k = 1 , i = 2 et j = 3 , la distance [i] [j] est -2 , ce qui n’est pas supérieur à la distance [i] [k] + distance [k] [j] = -2 + 0 = -2 . Donc, il restera inchangé. Là encore, lorsque k = 1 , i = 4 et j = 2 , la distance [i] [j] = infini , qui est supérieure à la distance [i] [k] + distance [k] [j] = 1 + 3 = 4 . On met donc la distance [i] [j] = 4 et on met le chemin [i] [j] = chemin [k] [j] = 1 . Cela signifie que pour aller du sommet 4 au sommet 2 , le chemin 4-> 1> 2 est plus court que le chemin existant. C'est ainsi que nous remplissons les deux matrices. Le calcul pour chaque étape est indiqué ici . Après avoir apporté les modifications nécessaires, nos matrices ressembleront à ceci:

+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|     |  1  |  2  |  3  |  4  |            |     |  1  |  2  |  3  |  4  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  1  |  0  |  3  |  1  |  3  |            |  1  |  N  |  1  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  2  |  1  |  0  | -2  |  0  |            |  2  |  4  |  N  |  2  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  3  |  3  |  6  |  0  |  2  |            |  3  |  4  |  1  |  N  |  3  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
|  4  |  1  |  4  |  2  |  0  |            |  4  |  4  |  1  |  2  |  N  |
+-----+-----+-----+-----+-----+            +-----+-----+-----+-----+-----+
            distance                                     path

C'est notre matrice de distance la plus courte. Par exemple, la distance la plus courte entre 1 et 4 est 3 et la distance la plus courte entre 4 et 3 est 2 . Notre pseudo-code sera:

Procedure Floyd-Warshall(Graph):
for k from 1 to V     // V denotes the number of vertex
    for i from 1 to V
       for j from 1 to V
           if distance[i][j] > distance[i][k] + distance[k][j]
               distance[i][j] := distance[i][k] + distance[k][j]
               path[i][j] := path[k][j]
           end if
       end for
    end for
end for

Imprimer le chemin:

Pour imprimer le chemin, nous allons vérifier la matrice Path . Pour imprimer le chemin de u à v , nous allons commencer par le chemin [u] [v] . Nous allons continuer à changer v = path [u] [v] jusqu'à ce que nous trouvions le chemin [u] [v] = u et poussez toutes les valeurs du chemin [u] [v] dans une pile. Après avoir trouvé u , nous allons imprimer u et commencer à extraire des éléments de la pile et les imprimer. Cela fonctionne parce que la matrice de chemin stocke la valeur du sommet qui partage le plus court chemin vers v depuis n'importe quel autre nœud. Le pseudo-code sera:

Procedure PrintPath(source, destination):
s = Stack()
S.push(destination)
while Path[source][destination] is not equal to source
    S.push(Path[source][destination])
    destination := Path[source][destination]
end while
print -> source
while S is not empty
    print -> S.pop
end while

Trouver un cycle de bord négatif:

Pour savoir s'il existe un cycle de front négatif, nous devons vérifier la diagonale principale de la matrice de distance . Si une valeur sur la diagonale est négative, cela signifie qu'il y a un cycle négatif dans le graphique.

Complexité:

La complexité de l'algorithme de Floyd-Warshall est O (V³) et la complexité de l'espace est: O (V²) .