Algoritmo de Floyd-Warshall

Na ciência da computação, o algoritmo de Floyd-Warshall (também conhecido como: Floyd's algorithmRoy–Warshall algorithmRoy–Floyd algorithm, ou WFI algorithm) é um algoritmo que resolve o problema de calcular o caminho mais curto entre todos os pares de vértices em um grafo orientado (com direção) e valorado (com peso). O algoritmo Floyd-Warshall foi publicado por Robert Floyd em 1962. Este algoritmo é o mesmo que foi publicado por Bernard Roy em 1959 e também por Stephen Warshall em 1962 para determinar o fechamento transitivo de um grafo.[1] O formato atual do algoritmo de Floyd-Warshall com três loops de repetição foi descrito por Peter Ingerman em 1962.

O algoritmo é um bom exemplo de programação dinâmica.

Definição

O algoritmo de Floyd-Warshall recebe como entrada uma matriz de adjacência que representa um grafo orientado e valorado. O valor de um caminho entre dois vértices é a soma dos valores de todas as arestas ao longo desse caminho. As arestas do grafo podem ter valores negativos, mas o grafo não pode conter nenhum ciclo de valor negativo. O algoritmo calcula, para cada par de vértices, o menor de todos os caminhos entre os vértices. Por exemplo, o caminho de menor custo. Sua ordem de complexidade é .

O algoritmo se baseia nos passos abaixo:

  • Assumindo que os vértices de um grafo orientado são , considere um subconjunto ;
  • Para qualquer par de vértices em , considere todos os caminhos de a cujos vértices intermédios pertencem ao subconjunto , e como o mais curto de todos eles;
  • O algoritmo explora um relacionamento entre o caminho e os caminhos mais curtos de a com todos os vértices intermédios em ;
  • O relacionamento depende de ser ou não um vértice intermédio do caminho .

Abaixo segue uma implementação em pseudocódigo do algoritmo de Floyd-Warshall:

ROTINA fw(Inteiro[1..n,1..n] grafo)
    # Inicialização
    VAR Inteiro[1..n,1..n] dist := grafo
    VAR Inteiro[1..n,1..n] pred
    PARA i DE 1 A n
        PARA j DE 1 A n
            SE dist[i,j] < Infinito ENTÃO
                pred[i,j] := i
    # Laço principal do algoritmo
    PARA k DE 1 A n
        PARA i DE 1 A n
            PARA j DE 1 A n
                SE dist[i,j] > dist[i,k] + dist[k,j] ENTÃO
                    dist[i,j] = dist[i,k] + dist[k,j]
                    pred[i,j] = pred[k,j]
    RETORNE dist
En otros idiomas