Algorithme de Floyd Warshall

Confus de choisir le chemin le plus court entre votre emplacement et votre destination…. Alors, vous devriez connaître cet algorithme.

• L’algorithme de Floyd-Warshall est utilisé pour trouver les chemins les plus courts entre toutes les paires de sommets dans un graphe, où chaque arête du graphe a un poids qui est positif ou négatif.
• Le plus grand avantage de l’utilisation de cet algorithme est que toutes les plus courtes distances entre 2 sommets quelconques pourraient être calculées en O(V3), où V est le nombre de sommets dans un graphe.
• L’algorithme de Floyd-Warshall est également appelé algorithme de Floyd, algorithme de Roy-Floyd, algorithme de Roy-Warshall ou algorithme WFI.
• Cet algorithme suit l’approche de programmation dynamique pour trouver les plus courts chemins.

Algorithme

Pour un graphe à N sommets :

Etape 1 : Initialiser les plus courts chemins entre 2 sommets quelconques avec Infini.

Etape 2 : Trouver tous les plus courts chemins par paire qui utilisent 0 sommet intermédiaire, puis trouver les plus courts chemins qui utilisent 1 sommet intermédiaire et ainsi de suite… jusqu’à utiliser tous les N sommets comme nœuds intermédiaires.

Étape 3 : Minimiser les plus courts chemins entre 2 paires quelconques dans l’opération précédente.

Étape 4 : Pour 2 sommets quelconques (i,j) , il faut en fait minimiser les distances entre cette paire en utilisant les K premiers nœuds, donc le plus court chemin sera : min(dist+dist,dist).

dist représente le plus court chemin qui utilise seulement les K premiers sommets, dist représente le plus court chemin entre la paire k,j. Comme le plus court chemin sera une concaténation du plus court chemin de i à k, puis de k à j.

for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
dist = min( dist, dist + dist );
}
}
}

Exemple

Disons que le graphe donné est :

Suivons les étapes ci-dessous pour trouver le plus court chemin entre toutes les paires de sommets.

1. Créer une matrice A0 de dimension n*n où n est le nombre de sommets. La ligne et la colonne sont indexées respectivement i et j. i et j sont les sommets du graphe.

Chaque cellule A est remplie avec la distance du sommet ith au sommet jth. S’il n’y a pas de chemin du sommet ith au sommet jth, la cellule est laissée à l’infini.

2. Maintenant, créez une matrice A1 en utilisant la matrice A0. Les éléments de la première colonne et de la première ligne sont laissés tels quels. Les cellules restantes sont remplies de la manière suivante.

Laissez k être le sommet gelé dans le plus court chemin de la source à la destination. Dans cette étape, k est le premier sommet.A est rempli avec (A + A) if (A > A + A).

C’est-à-dire que si la distance directe de la source à la destination est plus grande que le chemin passant par le sommet k, alors la cellule est remplie avec A + A.

Dans cette étape, k est le sommet 1. On calcule la distance du sommet source au sommet destination en passant par ce sommet k.

Par exemple : Pour A1, la distance directe du sommet 2 au 4 est 4 et la somme de la distance du sommet 2 au 4 en passant par le sommet (c’est-à-dire du sommet 2 au 1 et du sommet 1 au 4) est 7. Depuis 4 < 7, A0 est rempli avec 4.

3. De la même manière, A2 est créé en utilisant A3. Les éléments de la deuxième colonne et de la deuxième ligne sont laissés tels quels.

Dans cette étape, k est le deuxième sommet (c’est-à-dire le sommet 2). Les autres étapes sont les mêmes que celles de l’étape 2.

4. De même, A3 et A4 est également créé.

A4 donne le plus court chemin entre chaque paire de sommets.

Confus de sélectionner le plus court chemin, puis d’utiliser le code ci-dessous pour le trouver. Mais entrez les distances correctes.

Complexité temporelle

Il y a trois boucles. Chaque boucle a des complexités constantes. Donc, la complexité temporelle de l’algorithme de Floyd-Warshall est O(n3).

Complexité spatiale

La complexité spatiale de l’algorithme de Floyd-Warshall est O(n2).