Algoritmo Floyd-Warshall

En este tutorial, aprenderá cómo funciona el algoritmo floyd-warshall. Además, encontrará ejemplos prácticos del algoritmo floyd-warshall en C, C ++, Java y Python.

El algoritmo de Floyd-Warshall es un algoritmo para encontrar el camino más corto entre todos los pares de vértices en un gráfico ponderado. Este algoritmo funciona tanto para los gráficos ponderados dirigidos como para los no dirigidos. Pero, no funciona para los gráficos con ciclos negativos (donde la suma de los bordes en un ciclo es negativa).

Un gráfico ponderado es un gráfico en el que cada borde tiene un valor numérico asociado.

El algoritmo de Floyd-Warhshall también se denomina algoritmo de Floyd, algoritmo de Roy-Floyd, algoritmo de Roy-Warshall o algoritmo WFI.

Este algoritmo sigue el enfoque de programación dinámica para encontrar los caminos más cortos.

¿Cómo funciona el algoritmo Floyd-Warshall?

Sea el gráfico dado:

Gráfico inicial

Siga los pasos a continuación para encontrar la ruta más corta entre todos los pares de vértices.

  1. Cree una matriz de dimensión donde n es el número de vértices. La fila y la columna están indexadas como i y j respectivamente. i y j son los vértices del gráfico. Cada celda A (i) (j) se llena con la distancia del vértice al vértice. Si no hay una ruta de vértice a vértice, la celda se deja como infinito. Llene cada celda con la distancia entre el i y el j en el vérticeA0n*n
    ithjthithjth
  2. Ahora, cree una matriz usando matrix . Los elementos de la primera columna y la primera fila se dejan como están. Las celdas restantes se llenan de la siguiente manera. Sea k el vértice intermedio en el camino más corto desde el origen al destino. En este paso, k es el primer vértice. está lleno de . Es decir, si la distancia directa desde la fuente hasta el destino es mayor que la ruta a través del vértice k, entonces la celda se rellena con . En este paso, k es el vértice 1. Calculamos la distancia desde el vértice de origen al vértice de destino a través de este vértice k. Calcule la distancia desde el vértice de origen al vértice de destino a través de este vértice k Por ejemplo: ParaA1A0
    A(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 distancia directa del vértice 2 al 4 es 4 y la suma de la distancia del vértice 2 al 4 a través del vértice (es decir, del vértice 2 al 1 y del vértice 1 al 4) es 7. Dado que 4 < 7, se rellena con 4.A0(2, 4)
  3. Del mismo modo, se crea utilizando . Los elementos de la segunda columna y la segunda fila se dejan como están. En este paso, k es el segundo vértice (es decir, el vértice 2). Los pasos restantes son los mismos que en el paso 2 . Calcule la distancia desde el vértice de origen al vértice de destino a través de este vértice 2A2A3
  4. Del mismo modo, y también se crea. Calcule la distancia desde el vértice de origen al vértice de destino a través de este vértice 3 Calcule la distancia desde el vértice de origen al vértice de destino a través de este vértice 4A3A4
  5. A4 da el camino más corto entre cada par de vértices.

Algoritmo Floyd-Warshall

n = no de vértices A = matriz de dimensión n * n para k = 1 an para i = 1 an para j = 1 an A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) devuelve A

Ejemplos de Python, Java y 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); )

Complejidad del algoritmo de Floyd Warshall

Complejidad del tiempo

Hay tres bucles. Cada bucle tiene complejidades constantes. Entonces, la complejidad de tiempo del algoritmo Floyd-Warshall es .O(n3)

Complejidad espacial

La complejidad espacial del algoritmo Floyd-Warshall es .O(n2)

Aplicaciones del algoritmo Floyd Warshall

  • Para encontrar el camino más corto es un gráfico dirigido
  • Para encontrar el cierre transitivo de grafos dirigidos
  • Para encontrar la inversión de matrices reales
  • Para probar si un gráfico no dirigido es bipartito

Articulos interesantes...