Buscar

09 floyd warshall

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 34 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

Otimização em Redes
Allexandre Fortes S. Reis
Coordenadoria de Engenharia de Produção
Departamento de Engenharia Mecânica
Campus Santo Antônio
Universidade Federal de São João Del Rei
5 de outubro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 1 / 32
Conteúdo
1
Algoritmo de Floyd-Warshall
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 2 / 32
Algoritmo de Floyd-Warshall
Quem são os autores?
i. Proposto por Robert Floyd em 1962 e é baseado no algoritmo de...;
ii. Stephen Warshall do mesmo ano para cálculo de fechos transitivos em grafos;
iii. Comumente chamado de Algoritmo de Floyd-Warshall
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 3 / 32
Algoritmo de Floyd-Warshall
Princípio
i) O algoritmo calcula o menor caminho entre todos os pares de vértices de um grafo
direcionado e ponderado que eventualmente possua arcos com peso negativo, mas
que não possua ciclos de custo negativo;
ii) O algoritmo compara os caminhos entre os vértices i e j passando por k vértices
intermediários, k = 1, . . . , n;
iii) Em outras palavras, todos os caminhos entre cada par de vértices são analisados;
iv) Uma matriz armazena o valor dos menores caminhos entre os vértices, porém, não
há informação sobre composição do caminho.
v) Baseado na ideia de recorrência:
I
Seja dist(i, j, k) o comprimento do caminho mais curto entre i e j tal que apenas os
nós 1 . . . , k podem ser usados como intermediários;
dist(i, j, k + 1) = min{dist(i, j, k), dist(i, k + 1, k) + dist(k + 1, j, k)}
I
O algoritmo calcula a recorrência acima para k = 1, . . . , n..
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 4 / 32
Algoritmo de Floyd-Warshall
Detecção de Ciclos de Custo Negativo
i Caso haja valores negativos na diagonal principal da matriz L (inclusive durante a
execução do algoritmo), significa que o vértice relacionado está contido em um ciclo
de custo negativo;
ii Em outras palavras, é possível sair do vértice, percorrer parte do grafo e retornar ao
vértice inicial com custo negativo;
iii Algumas versões do algoritmo consideram que não haverá ciclos de custo negativo e
definem inicialmente a distância de um vértice para si próprio como −∞, implicando
em não haver atualização possível.
Caminhos
i Conforme visto, não são armazenadas informações sobre quais vértices compõem os
menores caminhos calculados, no entanto, o algoritmo pode ser modificado;
ii Não é necessário, entretanto, armazenar de fato todos os vértices dos menores cami-
nhos, implicando na necessidade de uma matriz tridimensional;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 5 / 32
Algoritmo de Floyd-Warshall
Detecção de Ciclos de Custo Negativo
i Caso haja valores negativos na diagonal principal da matriz L (inclusive durante a
execução do algoritmo), significa que o vértice relacionado está contido em um ciclo
de custo negativo;
ii Em outras palavras, é possível sair do vértice, percorrer parte do grafo e retornar ao
vértice inicial com custo negativo;
iii Algumas versões do algoritmo consideram que não haverá ciclos de custo negativo e
definem inicialmente a distância de um vértice para si próprio como −∞, implicando
em não haver atualização possível.
Caminhos
i Conforme visto, não são armazenadas informações sobre quais vértices compõem os
menores caminhos calculados, no entanto, o algoritmo pode ser modificado;
ii Não é necessário, entretanto, armazenar de fato todos os vértices dos menores cami-
nhos, implicando na necessidade de uma matriz tridimensional;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 5 / 32
Algoritmo de Floyd-Warshall
Terminologia
L : Matriz que armazena os menores caminhos entre os vértices:
I
Inicialmente, L é inicializada com os pesos dos arcos do grafo (dij);
I
Caso não haja arco entre dois vértices i e j, dij =∞.
lij : elemento da matriz L na linha i e coluna j.
Entrada: Grafo G = (V,E), matriz de distâncias D = [dij ], ∀(i, j) ∈ E
1 L← D;
2 para k ← 1 até n faça
3 para i← 1 até n faça
4 para j ← 1 até n faça
5 se lij > lik + lkj então
6 lij ← lik + lkj ;
7 fim
8 fim
9 fim
10 fim
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 6 / 32
Algoritmo de Floyd-Warshall
Terminologia
L : Matriz que armazena os menores caminhos entre os vértices:
I
Inicialmente, L é inicializada com os pesos dos arcos do grafo (dij);
I
Caso não haja arco entre dois vértices i e j, dij =∞.
lij : elemento da matriz L na linha i e coluna j.
Entrada: Grafo G = (V,E), matriz de distâncias D = [dij ], ∀(i, j) ∈ E
1 L← D;
2 para k ← 1 até n faça
3 para i← 1 até n faça
4 para j ← 1 até n faça
5 se lij > lik + lkj então
6 lij ← lik + lkj ;
7 fim
8 fim
9 fim
10 fim
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 6 / 32
Exemplo
Grafo G usado como exemplo e abaixo a matriz L inicial
1 2 3 4 5 6
1 ∞ 1 ∞ ∞ ∞ ∞
2 ∞ ∞ 1 3 2 ∞
3 3 ∞ ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 7 / 32
Exemplo
k = 1, i = 1. Sem alterações na matriz.
j = 1, l11 = min{l11, (l11 + l11)} =∞
j = 2, l12 = min{l12, (l11 + l12)} = 1
j = 3, l13 = min{l13, (l11 + l13)} =∞
j = 4, l14 = min{l14, (l11 + l14)} =∞
j = 5, l15 = min{l15, (l11 + l15)} =∞
j = 6, l16 = min{l16, (l11 + l16)} =∞
1 2 3 4 5 6
1 ∞ 1 ∞ ∞ ∞ ∞
2 ∞ ∞ 1 3 2 ∞
3 3 ∞ ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 8 / 32
Exemplo
k = 1, i = 2. Sem alterações na matriz.
j = 1, l21 = min{l21, (l21 + l11)} =∞
j = 2, l22 = min{l22, (l21 + l12)} =∞
j = 3, l23 = min{l23, (l21 + l13)} = 1
j = 4, l24 = min{l24, (l21 + l14)} = 3
j = 5, l25 = min{l25, (l21 + l15)} = 2
j = 6, l26 = min{l26, (l21 + l16)} =∞
1 2 3 4 5 6
1 ∞ 1 ∞ ∞ ∞ ∞
2 ∞ ∞ 1 3 2 ∞
3 3 ∞ ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 9 / 32
Exemplo
k = 1, i = 3. Matriz é alterada!
j = 1, l31 = min{l31, (l31 + l11)} = 3
j = 2, l32 = min{l32, (l31 + l12)} = 4
j = 3, l33 = min{l33, (l31 + l13)} =∞
j = 4, l34 = min{l34, (l31 + l14)} = 2
j = 5, l35 = min{l35, (l31 + l15)} =∞
j = 6, l36 = min{l36, (l31 + l16)} =∞
1 2 3 4 5 6
1 ∞ 1 ∞ ∞ ∞ ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 10 / 32
Exemplo
Acelerando...
Não haverá alterações para as iterações i = 4, 5, 6.
Serão apresentas somente somente as iterações do algoritmo que ocorrem
alterações na matriz L
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 11 / 32
Exemplo
k = 2, i = 1. Matriz é alterada!
j = 1, l11 = min{l11, (l12 + l21)} =∞
j = 2, l12 = min{l12, (l12 + l22)} = 1
j = 3, l13 = min{l13, (l12 + l23)} = 2
j = 4, l14 = min{l14, (l12 + l24)} = 4
j = 5, l15 = min{l15, (l12 + l25)} = 3
j = 6, l16 = min{l16, (l12 + l26)} =∞
1 2 3 4 5 6
1 ∞ 1 ∞ ∞ ∞ ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 12 / 32
Exemplo
k = 2, i = 3. Matriz é alterada!
j = 1, l31 = min{l31, (l32 + l21)} = 3
j = 2, l32 = min{l32, (l32 + l22)} = 4
j = 3, l33 = min{l33, (l32 + l23)} = 5
j = 4, l34 = min{l34, (l32 + l24)} = 2
j = 5, l35 = min{l35, (l32 + l25)} = 6
j = 6, l36 = min{l36, (l32 + l26)} =∞
1 2 3 4 5 6
1 ∞ 1 2 4 3 ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 ∞ 2 ∞ ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes5 de outubro de 2017 13 / 32
Exemplo
Matriz para k = 2
1 2 3 4 5 6
1 ∞ 1 2 4 3 ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 14 / 32
Exemplo
k = 3, i = 1. Matriz é alterada!
j = 1, l11 = min{l11, (l13 + l31)} = 5
j = 2, l12 = min{l12, (l13 + l32)} = 1
j = 3, l13 = min{l13, (l13 + l33)} = 2
j = 4, l14 = min{l14, (l13 + l34)} = 4
j = 5, l15 = min{l15, (l13 + l35)} = 3
j = 6, l16 = min{l16, (l13 + l36)} =∞
1 2 3 4 5 6
1 ∞ 1 2 4 3 ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 15 / 32
Exemplo
k = 3, i = 2. Matriz é alterada!
j = 1, l21 = min{l21, (l23 + l31)} = 4
j = 2, l22 = min{l22, (l23 + l32)} = 5
j = 3, l23 = min{l23, (l23 + l33)} = 1
j = 4, l24 = min{l24, (l23 + l34)} = 3
j = 5, l25 = min{l25, (l23 + l35)} = 2
j = 6, l26 = min{l26, (l23 + l36)} =∞
1 2 3 4 5 6
1 5 1 2 4 3 ∞
2 ∞ ∞ 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 16 / 32
Exemplo
Matriz para k = 3
1 2 3 4 5 6
1 5 1 2 4 3 ∞
2 4 5 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 17 / 32
Exemplo
k = 4, i = 1. Matriz é alterada!
j = 1, l11 = min{l11, (l14 + l41)} = 5
j = 2, l12 = min{l12, (l14 + l42)} = 1
j = 3, l13 = min{l13, (l14 + l43)} = 2
j = 4, l14 = min{l14, (l14 + l44)} = 4
j = 5, l15 = min{l15, (l14 + l45)} = 3
j = 6, l16 = min{l16, (l14 + l46)} = 6
1 2 3 4 5 6
1 5 1 2 4 3 ∞
2 4 5 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 18 / 32
Exemplo
k = 4, i = 2. Matriz é alterada!
j = 1, l21 = min{l21, (l24 + l41)} = 4
j = 2, l22 = min{l22, (l24 + l42)} = 5
j = 3, l23 = min{l23, (l24 + l43)} = 1
j = 4, l24 = min{l24, (l24 + l44)} = 3
j = 5, l25 = min{l25, (l24 + l45)} = 2
j = 6, l26 = min{l26, (l24 + l46)} = 5
1 2 3 4 5 6
1 5 1 2 4 3 6
2 4 5 1 3 2 ∞
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 19 / 32
Exemplo
k = 4, i = 3. Matriz é alterada!
j = 1, l31 = min{l31, (l34 + l41)} = 3
j = 2, l32 = min{l32, (l34 + l42)} = 4
j = 3, l33 = min{l33, (l34 + l43)} = 5
j = 4, l34 = min{l34, (l34 + l44)} = 2
j = 5, l35 = min{l35, (l34 + l45)} = 6
j = 6, l36 = min{l36, (l34 + l46)} = 4
1 2 3 4 5 6
1 5 1 2 4 3 6
2 4 5 1 3 2 5
3 3 4 5 2 6 ∞
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 20 / 32
Exemplo
k = 4, i = 5. Matriz é alterada!
j = 1, l51 = min{l51, (l54 + l41)} =∞
j = 2, l52 = min{l52, (l54 + l42)} =∞
j = 3, l53 = min{l53, (l54 + l43)} =∞
j = 4, l54 = min{l54, (l54 + l44)} = −3
j = 5, l55 = min{l55, (l54 + l45)} =∞
j = 6, l56 = min{l56, (l54 + l46)} = −1
1 2 3 4 5 6
1 5 1 2 4 3 6
2 4 5 1 3 2 5
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ ∞
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 21 / 32
Exemplo
k = 4
1 2 3 4 5 6
1 5 1 2 4 3 6
2 4 5 1 3 2 5
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ −1
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 22 / 32
Exemplo
k = 5, i = 1. Matriz é alterada!
j = 1, l11 = min{l11, (l15 + l51)} = 5
j = 2, l12 = min{l12, (l15 + l52)} = 1
j = 3, l13 = min{l13, (l15 + l53)} = 2
j = 4, l14 = min{l14, (l15 + l54)} = 0
j = 5, l15 = min{l15, (l15 + l55)} = 3
j = 6, l16 = min{l16, (l15 + l56)} = 2
1 2 3 4 5 6
1 5 1 2 4 3 6
2 4 5 1 3 2 5
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 23 / 32
Exemplo
k = 5, i = 2. Matriz é alterada!
j = 1, l21 = min{l21, (l25 + l51)} = 4
j = 2, l22 = min{l22, (l25 + l52)} = 5
j = 3, l23 = min{l23, (l25 + l53)} = 1
j = 4, l24 = min{l24, (l25 + l54)} = −1
j = 5, l25 = min{l25, (l25 + l55)} = 2
j = 6, l26 = min{l26, (l25 + l56)} = 1
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 3 2 5
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 24 / 32
Exemplo
k = 5, i = 6. Matriz é alterada!
j = 1, l21 = min{l21, (l25 + l51)} =∞
j = 2, l22 = min{l22, (l25 + l52)} =∞
j = 3, l23 = min{l23, (l25 + l53)} =∞
j = 4, l24 = min{l24, (l25 + l54)} = 0
j = 5, l25 = min{l25, (l25 + l55)} = 3
j = 6, l26 = min{l26, (l25 + l56)} = 2
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 −1 2 1
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ ∞ 3 ∞
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 25 / 32
Exemplo
k = 5
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 −1 2 1
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 26 / 32
Exemplo
k = 6, i = 4. Matriz é alterada!
j = 1, l41 = min{l41, (l46 + l61)} =∞
j = 2, l42 = min{l42, (l46 + l62)} =∞
j = 3, l43 = min{l43, (l46 + l63)} =∞
j = 4, l44 = min{l44, (l46 + l64)} = 2
j = 5, l45 = min{l45, (l46 + l65)} = 5
j = 6, l46 = min{l46, (l46 + l66)} = 4
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 -1 2 1
3 3 4 5 2 6 4
4 ∞ ∞ ∞ ∞ ∞ 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 27 / 32
Exemplo
k = 6, i = 5. Matriz é alterada!
j = 1, l51 = min{l51, (l56 + l61)} =∞
j = 2, l52 = min{l52, (l56 + l62)} =∞
j = 3, l53 = min{l53, (l56 + l63)} =∞
j = 4, l54 = min{l54, (l56 + l64)} = −3
j = 5, l55 = min{l55, (l56 + l65)} = 2
j = 6, l56 = min{l56, (l56 + l66)} = −1
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 -1 2 1
3 3 4 5 2 6 4
4 ∞ ∞ ∞ 2 5 2
5 ∞ ∞ ∞ -3 ∞ -1
6 ∞ ∞ ∞ 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 28 / 32
Exemplo
k = 6
1 2 3 4 5 6
1 5 1 2 0 3 2
2 4 5 1 -1 2 1
3 3 4 5 2 6 4
4 ∞ ∞ ∞ 2 5 2
5 ∞ ∞ ∞ -3 2 -1
6 ∞ ∞ ∞ 0 3 2
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 29 / 32
Exercício
Execute o algoritmo de Floyd-Warshall para o grafo acima.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 30 / 32
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 31 / 32
Referências
(1) Notas de aula Professor Dr. Marco Antônio Carvalho (DECOM/UFOP);
(2) Notas de aula Professor Dr. Gustavo Peixoto (DECOM/UFOP);
(3) Goldbarg, Marco e Goldbarg, Elizabeth. Grafos: Conceitos, algoritmos e apli-
cações (2012);
(4) Taha, Hamdy. Pesquisa Operacional (2008);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 5 de outubro de 2017 32 / 32
	Algoritmo de Floyd-Warshall

Outros materiais