floyd-warshall-121215042832-phpapp02

Prévia do material em texto

UNIVERSIDADE FEDERAL DE ALFENAS Teoria dos Grafos
Algoritmo de Floyd-Warshall
Discentes: Jéverson Abreu, João A. Silva,
Sueli Perpétua, Thalles Terra
Docente: Douglas Castilho
Disciplina: Teoria dos Grafos
23 de setembro de 2012
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 1 / 16
Introdução
Também conhecido como algoritmo de Floyd, algoritmo de
Roy-Floyd, algoritmo de Roy-Warshall ou algoritmo WFI;
Foi explicado por Bernard Roy em 1959 e publica 3 anos
mais tarde por Stephen Warshall e Robert Floyd.
É um algoritmo que resolve o problema de encontrar o menor
caminho entre todos os pares de vértices de um grafo orientado e
ponderado
Ele apenas encontra os valores de tais caminhos, e não
a seqüência de arestas a ser percorrida.
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 2 / 16
Outras Aplicações
Calcular o Fecho Transitivo de um grafo;
Verificar se um grafo não-dirigido é bipartido;
Achar um vértice central, isto é, aquele que minimiza a distância
máxima ou média entre todos os vértices;
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 3 / 16
Problema de se encontrar um vértice central
Poderíamos pensar, em como avaliar o melhor local para
instalarmos uma loja. Podemos definir como melhor local aquele
que diminui a distância entre a loja e locais estratégicos como:
Um bairro onde o consumo dos produtos vendidos por ela é alto;
Estabelicimentos que prestarão serviços para a loja;
Um local onde se tenha uma grande concentração de um público
alvo para a loja.
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 4 / 16
Menor caminho entre todos os vértices
Dado um grafo G direcionado e ponderado, encontrar para todo
par u, v de vértices um caminho mínimo de u a v.
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 5 / 16
Menor caminho entre todos os vértices
O algorimto de Floyd-Warshall tem como objetivo calcular o
caminho mínimo entre cada par de vértices de um grafo
O grafo pode conter arestas negativas
Não pode conter ciclos negativos
Utiliza técnica de programação dinâmica
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 6 / 16
Menor caminho entre todos os vértices
Entrada: matriz de adjacência representando os pesos das
arestas de um grafo orientado e satisfaça a seguinte condição:
yj =

0, se i = j ,
o peso da aresta orientada(i , j), se, i 6= j e (i , j) ∈ A,
∞, caso contrário.
Saída: Uma matriz quadrada D|V |X |V | onde cada célula dij contém
a distancia mínima entre o vétice i e j , onde a entrada dij contém
o peso do caminho mais curto do vértice i até o vértice j .
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 7 / 16
Menor caminho entre todos os vértices
func floyd-Warshall(caminho[][])
for k = 1 to n
for i = 1 to n
for j = 1 to n
caminho[i][j] = min(caminho[i][j], caminho[i][k]+caminho[k][j])
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 8 / 16
Menor caminho entre todos os vértices
func floyd-Warshall(caminho[][])
for k = 1 to n
for i = 1 to n
for j = 1 to n
caminho[i][j] = min(caminho[i][j], caminho[i][k]+caminho[k][j])
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 9 / 16
Acompanhamento
Matriz de adjacência de entrada
D(0) =
0 8 5
3 0 ∞
∞ 2 0
Após iteração sobre o primeiro vértice
D(1) =
0 8 5
3 0 8
∞ 2 0
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 10 / 16
Acompanhamento
Após iteração sobre o segundo vértice
D(2) =
0 8 5
3 0 8
5 2 0
Após iteração sobre o terceiro vértice
D(3) =
0 7 5
3 0 8
5 2 0
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 11 / 16
Complexidade
É fácil analisar o tempo de execução do algoritmo de
Floyd-warshall. O laço principal é executado n vezes e o laço
interno considera cada um dos O(n2) pares de vértices,
realizando um operação de tempo constante para cada par. Se
usarmos uma estrutura de dados como a matriz de adjacência,
temos um tempo de execução total de O(n3).
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 12 / 16
Bellman Ford x Dijkstra x Floyd-Warshall
BF Dijkstra FW
|V |O(|V ∗ A|) |V |O(|V |2 + |A| O(|V |3)
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 13 / 16
Considerações Finais
O Algoritmo de Floyd-Warshall e Bellman Ford trabalha com
arestas de peso negativo enquanto Dijkstra não.
Floyd-Warshall tem como saída uma matriz de caminho mínimos
já Bellman Ford e Dijkstra fornece um vetor.
No Dijkstra, é possível reproduzir o caminho, enquanto que o
Floyd-Warshall apenas fornece o caminho mais curto, e não a
sequência das arestas.
Bellman Ford aceita ciclo negativo enquanto Floyd-Warshall não.
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 14 / 16
Bibliografia
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; (2002).
Algoritmos - Teoria e Prática. Tradução da 2a edição americana.
Rio de Janeiro. Editora Campus
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 15 / 16
Perguntas???
Jéverson, João, Sueli, Thalles (Unifal-MG) 23 de setembro de 2012 16 / 16
	Main Talk
	Algoritmo de Floyd-Warshall