Algoritmo Floyd-Warshall Oficial

Prévia do material em texto

Algoritmo 
Floyd-Warshall
Disciplina: Algoritmo e Estrutura de Dados
Curso: Engenharia de Energia
Docente: Eduardo Braulio Wanderley Netto
Discentes: José Alyson Bezerra Santos e Sofia Rodrigues Oliveira Gonçalves
Sumário
Introdução
Aplicações
Vantagens e Desvantagens
Referências
Execução do Algoritmo
Introdução
Stephen 
Warshall
Robert Floyd 
Publicado em 1962. O algoritmo de Floyd-Warshall calcula os caminhos mais curtos entre todos os pares de vértices de um grafo
Admite arestas com peso negativo, mas não admite ciclos negativo
Bernad Roy*
Aplicações do Algoritmo Floyd-Warshall
Otimização de custos de rotas aeronáuticas internacionais
Busca da rota de menor caminho.
GPS
AERONAÚTICA
FARMÁCIA
Facilitar a localização e o trajeto dos clientes até uma farmácia. 
Floyd-Warshall
B
C
D
A
1
2
7
2
5
3
8
M4 =
A
B
C
D
A B C D
0
3
5
6
5
0
2
3
3
6
0
1
2
5
7
0
M0 =
A
B
C
D
A B C D
0
3
∞
7
8
0
2
∞
5
∞
0
1
2
∞
∞
0
Funcionamento do Algoritmo
B
C
A
x
x
x
x
x
M0 =
A
B
C
A B C 
x
x
x
x
x
x
x
x
x
M1 =
A
B
C
A B C 
x
x
x
x
x
x
x
x
x
M2 =
A
B
C
A B C 
x
x
x
x
x
x
x
x
x
M3 =
A
B
C
A B C 
x
x
x
x
x
x
x
x
x
M[B][C] > M[B][A] + M[A][C] 
i = B | j = C | k = A 
i = B | j = A | k = C 
i = C | j = B | k = A 
M[C][B] > M[C][A] + M[A][B] 
i = A | j = C | k = B 
M[A][C] > M[A][B] + M[B][C] 
i = C | j = A | k = B 
i = A | j = B | k = C 
M[A][B] > M[A][C] + M[C][B] 
M[i][j] > M[i][k] + M[k][j] é Verdadeiro? 
i = Linha | j = Coluna | k = Pivô 
Sim: M[i][j]=M[i][k]+M[k][j] 
Não: Mantem-se o valor
Exemplo Prático
B
C
A
2
8
1
5
4
M0 =
A
B
C
A B C 
0
5
8
4
0
1
2
∞
0
M1 =
A
B
C
A B C 
0
5
8
4
0
1
2
7
0
M2 =
A
B
C
A B C 
0
5
6
4
0
1
2
7
0
M3 =
A
B
C
A B C 
0
5
6
3
0
1
2
7
0
M[B][C] > M[B][A] + M[A][C] 
 1 > 4 + 8 
i = B | j = C | k = A 
i = B | j = A | k = C 
M[B][A] > M[B][C] + M[C][A] 
 4 > 1 + 2 
i = C | j = B | k = A 
M[C][B] > M[C][A] + M[A][B] 
 ∞ > 2 + 5 
i = A | j = C | k = B 
M[A][C] > M[A][B] + M[B][C] 
 8 > 5 + 1 
i = C | j = A | k = B 
M[C][A] > M[C][B] + M[B][A] 
 2 > 7 + 4 
i = A | j = B | k = C 
M[A][B] > M[A][C] + M[C][B] 
 5 > 6 + 7 
Exercício Proposto
B
C
A
4
12
2
9
8
M0 =
A
B
C
A B C 
0
9
12
8
0
2
4
∞
0
M1 =
A
B
C
A B C 
0
9
12
8
0
2
4
13
0
M2 =
A
B
C
A B C 
0
9
11
8
0
2
4
13
0
M3 =
A
B
C
A B C 
0
9
11
6
0
2
4
13
0
M[B][C] > M[B][A] + M[A][C] 
 2 > 8 + 12 
i = B | j = C | k = A 
i = B | j = A | k = C 
M[B][A] > M[B][C] + M[C][A] 
 8 > 2 + 4 
i = C | j = B | k = A 
M[C][B] > M[C][A] + M[A][B] 
 ∞ > 4 + 9 
i = A | j = C | k = B 
M[A][C] > M[A][B] + M[B][C] 
 12 > 9 + 2 
i = C | j = A | k = B 
M[C][A] > M[C][B] + M[B][A] 
 4 > 13 + 8 
i = A | j = B | k = C 
M[A][B] > M[A][C] + M[C][B] 
 9 > 11 + 13 
Fórmula: M[i][j] > M[i][k] + M[k][j]
Vantagens e Desvantagens
Eficiente para grafos densos (muitas arestas);
Determinação de todos os caminhos mais curtos;
Lida com arestas com peso negativo;
Identifica ciclos negativos.
VANTAGENS
DESVANTAGENS
Complexidade de tempo
Consumo de memória
Sensibilidade a ciclos negativos
Falta de detalhes sobre o caminho mais curto
Referências
PRIETO, Pedro S. Uma aplicação de teoria dos grafos para otimização de custos de rotas aeronáuticas internacionais. 2022. 
Virgínia Maia de Brito Fernandes et al. Algoritmo de Floyd-Warshall Utilizado no Mapeamento das Rotas de Farmácias. In: ANAIS DO SIMPÓSIO BRASILEIRO DE PESQUISA OPERACIONAL, 2020, João Pessoa. Campinas, Galoá, 2020. 
DAUDT, C.; MIRANDA, C. Análise da Complexidade do Algoritmo de Floyd-Warshall. Universidade Federal do Rio Grande do Sul, 2010.
image1.png
image2.gif
image3.jpeg
image4.png
image5.png
image6.png
image7.png