Algoritmo Floyd-Warshall

Neste tutorial, você aprenderá como o algoritmo floyd-warshall funciona. Além disso, você encontrará exemplos de funcionamento do algoritmo floyd-warshall em C, C ++, Java e Python.

Floyd-Warshall Algorithm é um algoritmo para encontrar o caminho mais curto entre todos os pares de vértices em um gráfico ponderado. Este algoritmo funciona para gráficos ponderados direcionados e não direcionados. Porém, não funciona para os gráficos com ciclos negativos (onde a soma das arestas de um ciclo é negativa).

Um gráfico ponderado é um gráfico em que cada aresta possui um valor numérico associado a ela.

O algoritmo Floyd-Warhshall também é chamado de algoritmo de Floyd, algoritmo de Roy-Floyd, algoritmo de Roy-Warshall ou algoritmo WFI.

Este algoritmo segue a abordagem de programação dinâmica para encontrar os caminhos mais curtos.

Como funciona o algoritmo Floyd-Warshall?

Deixe o gráfico dado ser:

Gráfico inicial

Siga as etapas abaixo para encontrar o caminho mais curto entre todos os pares de vértices.

  1. Crie uma matriz de dimensão onde n é o número de vértices. A linha e a coluna são indexadas como iej respectivamente. i e j são os vértices do gráfico. Cada célula A (i) (j) é preenchida com a distância do vértice ao vértice. Se não houver um caminho de vértice a vértice, a célula permanece infinita. Preencha cada célula com a distância entre o iº e o jº vérticeA0n*n
    ithjthithjth
  2. Agora, crie uma matriz usando matriz . Os elementos na primeira coluna e na primeira linha são deixados como estão. As células restantes são preenchidas da seguinte maneira. Seja k o vértice intermediário no caminho mais curto da origem ao destino. Nesta etapa, k é o primeiro vértice. é preenchido com . Ou seja, se a distância direta da origem ao destino for maior do que o caminho através do vértice k, a célula será preenchida com . Nesta etapa, k é o vértice 1. Calculamos a distância do vértice de origem ao vértice de destino através deste vértice k. Calcule a distância do vértice de origem ao vértice de destino através deste vértice k Por exemplo: 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), a distância direta do vértice 2 ao 4 é 4 e a soma da distância do vértice 2 ao 4 ao vértice (isto é, do vértice 2 ao 1 e do vértice 1 ao 4) é 7. Visto que 4 < 7, é preenchido com 4.A0(2, 4)
  3. Da mesma forma, é criado usando . Os elementos na segunda coluna e na segunda linha são deixados como estão. Nesta etapa, k é o segundo vértice (ou seja, vértice 2). As etapas restantes são iguais às da etapa 2 . Calcule a distância do vértice de origem ao vértice de destino através deste vértice 2A2A3
  4. Da mesma forma, e também é criado. Calcule a distância do vértice de origem ao vértice de destino através deste vértice 3 Calcule a distância do vértice de origem ao vértice de destino através deste vértice 4A3A4
  5. A4 fornece o caminho mais curto entre cada par de vértices.

Algoritmo Floyd-Warshall

n = não dos vértices A = matriz de dimensão n * n para k = 1 an para i = 1 an para j = 1 para n A k (i, j) = min (A k-1 (i, j) , A k-1 (i, k) + A k-1 (k, j)) retorna A

Exemplos de Python, Java e 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); )

Complexidade do algoritmo Floyd Warshall

Complexidade de tempo

Existem três loops. Cada loop tem complexidades constantes. Portanto, a complexidade de tempo do algoritmo Floyd-Warshall é .O(n3)

Complexidade do Espaço

A complexidade espacial do algoritmo Floyd-Warshall é .O(n2)

Aplicativos de algoritmo Floyd Warshall

  • Para encontrar o caminho mais curto é um gráfico direcionado
  • Para encontrar o fechamento transitivo de gráficos direcionados
  • Para encontrar a inversão de matrizes reais
  • Para testar se um gráfico não direcionado é bipartido

Artigos interessantes...