Escala
Pares encurtados
Pares verificados

  • Escala atual
  • Já foi escala
  • Par encurtado
  • Caminho
Um clique num nó define

Mais sobre o algoritmo de Floyd–Warshall

Algoritmo de Floyd–Warshall

A que distância fica cada cidade de todas as outras? O Floyd–Warshall responde de uma só vez, com uma tabela e três ciclos aninhados. Cada ronda permite mais um nó como escala e pergunta, para cada par, se o desvio por ele é mais curto. Avance passo a passo para ver a tabela a encher-se e as distâncias a descer. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A tabela contém a distância mais curta encontrada até agora entre cada par de nós; o número em cada aresta é o seu comprimento. Cada ronda permite mais um nó como escala pelo caminho, e cada passo mostra um par que fica mais curto através dele. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para ver no fim o caminho mais curto entre eles. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.

Como funciona

  1. Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
  2. Observe a tabela: a linha e a coluna da escala atual estão coloridas, e cada passo escreve uma distância mais curta.
  3. Escolha uma origem e um destino para ver no fim o caminho mais curto entre eles. Novo grafo cria outro grafo para experimentar.

Como funciona o Floyd–Warshall

Faça uma tabela com uma linha e uma coluna por nó. Escreva 0 na diagonal, o comprimento da aresta onde dois nós estão ligados, e infinito em todos os outros lugares. Depois tome cada nó k à vez como possível escala. Para cada par i, j, compare a distância de i a j na tabela com a distância de i a k mais a distância de k a j, e fique com a menor. Depois do último nó, cada entrada é a distância mais curta entre os seus dois nós.

Porque é que funciona

Depois da ronda de k, a tabela contém, para cada par, o caminho mais curto cujas escalas estão todas entre os nós tratados até agora. A ronda do nó seguinte só tem de decidir se esse nó ajuda: um caminho mais curto através dele é um caminho mais curto até ele mais um caminho mais curto a partir dele, ambos já na tabela. Esta forma de construir uma resposta grande a partir de respostas menores já encontradas chama-se programação dinâmica. Com arestas negativas continua a funcionar, e um número negativo na diagonal revela um ciclo negativo.

Perguntas frequentes

O que é o algoritmo de Floyd–Warshall?

Um algoritmo que encontra a distância mais curta entre cada par de nós num grafo ponderado. Mantém uma tabela de distâncias e, para cada nó à vez, verifica se passar por esse nó encurta algum par.

Quão rápido é o Floyd–Warshall?

Tem três ciclos aninhados sobre os n nós, por isso o trabalho cresce com n³, e a tabela precisa de n² entradas. Isso serve para grafos de algumas centenas de nós. Para grafos grandes e esparsos, correr o algoritmo de Dijkstra a partir de cada nó é mais rápido.

O Floyd–Warshall lida com arestas negativas?

Sim, desde que não haja um ciclo negativo. Se houver, alguma entrada da diagonal fica negativa, e é assim que o Floyd–Warshall o deteta.

Como obtenho os caminhos, e não só as distâncias?

Mantenha uma segunda tabela com o nó seguinte no caminho de i para j. Sempre que um par fica mais curto através de k, copie o nó seguinte de i em direção a k. Seguir essa tabela de i para j dá o caminho.

O meu grafo é enviado para algum lado?

Não. O grafo é criado e a tabela preenchida no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Ir para o editor