Dans ce didacticiel, vous apprendrez comment fonctionne l'algorithme floyd-warshall. Vous trouverez également des exemples fonctionnels de l'algorithme floyd-warshall en C, C ++, Java et Python.
L'algorithme Floyd-Warshall est un algorithme permettant de trouver le chemin le plus court entre toutes les paires de sommets dans un graphe pondéré. Cet algorithme fonctionne à la fois pour les graphiques pondérés dirigés et non dirigés. Mais, cela ne fonctionne pas pour les graphiques avec des cycles négatifs (où la somme des arêtes dans un cycle est négative).
Un graphique pondéré est un graphique dans lequel chaque arête est associée à une valeur numérique.
L'algorithme Floyd-Warhshall 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 chemins les plus courts.
Comment fonctionne l'algorithme Floyd-Warshall?
Soit le graphique donné:
Graphique initial
Suivez les étapes ci-dessous pour trouver le chemin le plus court entre toutes les paires de sommets.
- Créez une matrice de dimension où n est le nombre de sommets. La ligne et la colonne sont respectivement indexées comme i et j. i et j sont les sommets du graphe. Chaque cellule A (i) (j) est remplie avec la distance entre le sommet et le sommet. S'il n'y a pas de chemin d'un sommet à l'autre , la cellule est laissée à l'infini. Remplissez chaque cellule avec la distance entre le ième et le jième sommet
A0n*nithjthithjth
- Maintenant, créez une matrice à l' aide de matrice . 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. Soit k le sommet intermédiaire du chemin le plus court de la source à la destination. Dans cette étape, k est le premier sommet. est rempli de . Autrement dit, si la distance directe de la source à la destination est supérieure au chemin passant par le sommet k, alors la cellule est remplie . Dans cette étape, k est le sommet 1. Nous calculons la distance entre le sommet source et le sommet de destination en passant par ce sommet k. Calculez la distance entre le sommet source et le sommet de destination en passant par ce sommet k Par exemple: Pour
A1A0A(i)(j)(A(i)(k) + A(k)(j)) if (A(i)(j)> A(i)(k) + A(k)(j))A(i)(k) + A(k)(j)
A1(2, 4), la distance directe entre les sommets 2 et 4 est de 4 et la somme de la distance entre les sommets 2 et 4 et les sommets (c'est-à-dire entre les sommets 2 et 1 et entre les sommets 1 et 4) est de 7. Depuis4 < 7, est remplie de 4.A0(2, 4) - De même, est créé en utilisant . 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 étapes restantes sont les mêmes qu'à l' étape 2 . Calculez la distance entre le sommet source et le sommet de destination en passant par ce sommet 2
A2A3
- De même, et est également créé. Calculer la distance entre le sommet source et le sommet de destination en passant par ce sommet 3 Calculer la distance entre le sommet source et le sommet de destination en passant par ce sommet 4
A3A4
A4donne le chemin le plus court entre chaque paire de sommets.
Algorithme Floyd-Warshall
n = nombre de sommets A = matrice de dimension n * n pour k = 1 à n pour i = 1 à n pour j = 1 à n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) renvoie A
Exemples Python, Java et C / C ++
Python Java C C ++ # Floyd Warshall Algorithm in python # The number of vertices nV = 4 INF = 999 # Algorithm implementation def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G)) # Adding vertices individually for k in range(nV): for i in range(nV): for j in range(nV): distance(i)(j) = min(distance(i)(j), distance(i)(k) + distance(k)(j)) print_solution(distance) # Printing the solution def print_solution(distance): for i in range(nV): for j in range(nV): if(distance(i)(j) == INF): print("INF", end=" ") else: print(distance(i)(j), end=" ") print(" ") G = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)) floyd_warshall(G)
// Floyd Warshall Algorithm in Java class FloydWarshall ( final static int INF = 9999, nV = 4; // Implementing floyd warshall algorithm void floydWarshall(int graph()()) ( int matrix()() = new int(nV)(nV); int i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()()) ( for (int i = 0; i < nV; ++i) ( for (int j = 0; j < nV; ++j) ( if (matrix(i)(j) == INF) System.out.print("INF "); else System.out.print(matrix(i)(j) + " "); ) System.out.println(); ) ) public static void main(String() args) ( int graph()() = ( ( 0, 3, INF, 5 ), ( 2, 0, INF, 4 ), ( INF, 1, 0, INF ), ( INF, INF, 2, 0 ) ); FloydWarshall a = new FloydWarshall(); a.floydWarshall(graph); ) )
// Floyd-Warshall Algorithm in C #include // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
// Floyd-Warshall Algorithm in C++ #include using namespace std; // defining the number of vertices #define nV 4 #define INF 999 void printMatrix(int matrix()(nV)); // Implementing floyd warshall algorithm void floydWarshall(int graph()(nV)) ( int matrix(nV)(nV), i, j, k; for (i = 0; i < nV; i++) for (j = 0; j < nV; j++) matrix(i)(j) = graph(i)(j); // Adding vertices individually for (k = 0; k < nV; k++) ( for (i = 0; i < nV; i++) ( for (j = 0; j < nV; j++) ( if (matrix(i)(k) + matrix(k)(j) < matrix(i)(j)) matrix(i)(j) = matrix(i)(k) + matrix(k)(j); ) ) ) printMatrix(matrix); ) void printMatrix(int matrix()(nV)) ( for (int i = 0; i < nV; i++) ( for (int j = 0; j < nV; j++) ( if (matrix(i)(j) == INF) printf("%4s", "INF"); else printf("%4d", matrix(i)(j)); ) printf(""); ) ) int main() ( int graph(nV)(nV) = ((0, 3, INF, 5), (2, 0, INF, 4), (INF, 1, 0, INF), (INF, INF, 2, 0)); floydWarshall(graph); )
Complexité de l'algorithme Floyd Warshall
Complexité temporelle
Il y a trois boucles. Chaque boucle a des complexités constantes. Ainsi, la complexité temporelle de l'algorithme Floyd-Warshall est .O(n3)
Complexité spatiale
La complexité spatiale de l'algorithme Floyd-Warshall est .O(n2)
Applications de l'algorithme Floyd Warshall
- Pour trouver le chemin le plus court est un graphe orienté
- Pour trouver la fermeture transitive de graphes orientés
- Pour trouver l'inversion de matrices réelles
- Pour tester si un graphe non orienté est bipartite
