ENG1529 - 2012 Cap 3

Prévia do material em texto

Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 1
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes3 - Aplicações de Modelos de Redes
Problemas Estudados 
� Árvore de Cobertura Mínima
Dada uma rede com n nós como visitar todos com o menor custo possível?
• Algoritmo de Prim
• Algoritmo de Kruskal
� Caminho Mais Curto em uma Rede
Dada uma rede com n nós qual o caminho mais curto entre dois nós? (Caso particular)
• Algoritmo de Dijskstra
Dada uma rede com n nós qual o caminho mais curto entre todos os pares de nó? 
(Caso geral)
• Algoritmo de Floyd
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes3 - Aplicações de Modelos de Redes
Árvore de Cobertura ou Geradora
Pizzolato, 2003
Dado um Grafo completo
com 3 nós (n=3). nn-2 = 31 = 3 árvores de cobertura.
c
a
b c
a
b c
a
b c
a
b
A quantidade de árvores de cobertura (nn-2) será:
n = no de nós
Serão nn-2 = 42 = 16 árvores de cobertura.
c d
Para n = 4.
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
c d
a b
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima* - Definição 
O problema consiste na determinação de arcos que liguem todos os
nós de uma rede, de tal maneira que a soma de suas distâncias seja
mínima. Requer que cada par de nós esteja conectado por meio de
um caminho.
Uma ACM é uma árvore geradora cuja soma do comprimento de seus 
arcos é mínimo em G (N,A).
Não se deve incluir ciclos ou sub-
ciclos na solução do problema. 
Gonzalez adaptado de Pizzolato, 2003
Goldbarg e Luna, 2000
* Minimum Spanning Tree - MST
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Exemplo de Aplicação – Distribuição de Energia
Gonzalez adaptado de Pizzolato, 2003
Uma empresa telefônica precisa determinar a melhor alternativa para instalar
os cabos das linhas telefônicas de tal forma que todas as estações estejam
conectadas, mas minimizando o comprimento total dos cabos.
Distâncias entre Estações Telefônicas
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
3 - Aplicações de Modelos de Redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 2
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Alguns Tipos de Solução 
Os algoritmos de Kruskal e Prim são algoritmos clássicos que permitem 
uma solução rápida e eficiente para a ACM. 
Goldbarg e Luna, 2000
Prim:
• A árvore geradora é construída a partir de um arco, pelo acréscimo de novos arcos, 
aumentando-se a arborescência inicial até que todos os nós sejam incluídos.
• O algoritmo de Prim acha a árvore geradora mínima de maneira gulosa: começa 
com um único nó qualquer da árvore e, a cada passo, adiciona o nó que se liga a 
árvore através do menor arco até que todas os nós do grafo tenham sido incluídos. A 
estratégia é gulosa já que a cada passo é adicionado o arco de menor peso que liga 
um nó que está na árvore a um nó que não está.
Kruskal: podem ser desenvolvidas várias arborescências 
simultâneas até que uma só árvore inclua todos os nós. 
Em qualquer hipótese, 
o critério de inclusão de 
arcos nas 
arborescências é 
guloso.
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Algoritmo de Prim 
Passo 2: Se todos os nós estiverem conectados, pare. Se existirem nós 
ainda isolados, ir para o Passo 3.
Passo 3: Deve-se identificar dentre os nós ainda isolados aquele mais 
próximo do conjunto dos nós já conectados e conecta-lo. Depois deve-se 
voltar para o Passo 2.
Solução dos empates: Nos passos 1 e 3 poderíamos ter 2 ou mais nós empatados com a 
menor distância. Nestes casos, arbitra-se uma solução (um nó) para desfazer o empate. Assim 
mesmo, o algoritmo fornece a solução ótima. 
No entanto, a existência de empates é um sinal de que poderiam haver, mas não necessariamente, 
múltiplas soluções ótimas. Então, pode-se identificar soluções alternativas executando todas as 
maneiras possíveis de desfazer os empates e continuar com o procedimento até a finalização.
Gonzalez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Solução Algoritmo de Prim – (I)
Gutierez adaptado de Pizzolato, 2003
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Processo manual usando Grafos
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Passo 2: Se todos os nós estiverem conectados, pare. Se existirem nós ainda isolados, ir 
para o Passo 3.
Passo 3: Deve-se identificar dentre os nós ainda isolados aquele mais próximo do 
conjunto dos nós já conectados e conecta-lo. Depois deve-se voltar para o Passo 2.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Gutierez adaptado de Pizzolato, 2003
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
3 - Aplicações de Modelos de Redes
Árvore de Cobertura Mínima 
Solução Algoritmo de Prim – (II)
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 3
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Passo 2: Se todos os nós estiverem conectados, pare. Se existirem nós ainda isolados, ir 
para o Passo 3.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Gutierez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Passo 3: Deve-se identificar dentre os nós ainda isolados aquele mais próximo do 
conjunto dos nós já conectados e conecta-lo. Depois deve-se voltar para o Passo 2.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Árvore de Cobertura Mínima 
Solução Algoritmo de Prim – (III)
Departamento de Engenharia IndustrialIND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Gutierez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
Passo 2: Se todos os nós estiverem conectados, pare. Se existirem nós ainda isolados, ir 
para o Passo 3.
Passo 3: Deve-se identificar dentre os nós ainda isolados aquele mais próximo do 
conjunto dos nós já conectados e conecta-lo. Depois deve-se voltar para o Passo 2.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5 Árvore de Cobertura Mínima 
Solução Algoritmo de Prim – (IV)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Todos os nós se encontram agora conectados, portanto esta 
solução é a procurada para o problema (solução ótima). A 
distância total da árvore é de 14 unidades métricas.
Para realizar o controle dos
nós conectados e dos não
conectados enquanto se faz
a resolução pela forma
gráfica, pode-se, a cada
iteração, empregar a
seguinte notação:
ITERAÇÃO C (Conjunto dos 
Nós Conectados)
Ĉ (Conjunto Nós 
não Conectados) Distância
1 A B, C, D, E, F, G 0
2 A, B C, D, E, F, G 2
3 A, B, D C, E, F, G 4
4 A, B, D, C E, F, G 5
5 A, B, D, C, E F, G 8
6 A, B, D, C, E, F G 9
7 A, B, D, C, E, F, G 14
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Gutierez adaptado de Pizzolato, 2003
• As arborescências 
consideram a orientação dos 
arcos.
• Uma árvore de rota mínima é 
arborescência.
3 - Aplicações de Modelos de Redes
Árvore de Cobertura Mínima 
Solução Algoritmo de Prim – (V)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Algoritmo de Kruskal 
Passo 1: Ordenar os arcos do grafo segundo suas distâncias.
Passo 2: Tomar os primeiros n-1 arcos que não formam ciclo, com os 
outros já escolhidos na árvore, onde n é o número de nós.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
3 - Aplicações de Modelos de Redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 4
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Passo 1: Ordenar os arcos do grafo segundo suas distâncias.
Árvore de Cobertura Mínima – Kruskal
Solução (I)
A1
A2
A3
A4
A5
A6
A8
A9
A7
A10
A11
A12
A10 A5 A1 A4 A9 A3 A7 A8 A2 A11 A6 A12
1 1 2 2 3 4 4 4 5 5 7 7
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima – Kruskal
Solução (II)
Passo 2: Tomar os primeiros n-1 
arcos que não formam ciclo, com os 
outros já escolhidos na árvore, onde é 
o número de nós.
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
A1
A2
A3
A4
A5
A6
A8
A9
A7
A10
A11
A12
A10 A5 A1 A4 A9 A3 A7 A8 A2 A11 A6 A12
1 1 2 2 3 4 4 4 5 5 7 7
Tomam-se os primeiros arcos que não formam ciclo:
A10, A5, A1, A4, A9
A3 – forma ciclo com A1, A4, A5
A7 – forma ciclo com A5 e A9
A8 – forma ciclo com A9 e A10
A2 – forma ciclo com A1 e A4
A11 – com esse último arco forma-se a árvore de cobertura 
mínima A10, A5, A1, A4, A9, A11
Sendo n o número total de
nós na rede, n – 1 = 6
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Solução do Algoritmo de Kruskal – (I)
B
D
C
E
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
D
C
E
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
OU
1a inclusão de arco
B
D
C
E
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
2a inclusão de arco
B
D
C
E
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
D
C
E
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
OU
3a inclusão de arco
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
4a inclusão de arco 5a inclusão de arco Não podem ser incluídos pois fecham ciclos
Árvore de Cobertura Mínima 
Solução do Algoritmo de Kruskal – (II)
B
D
C
G
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
B
C
F
E
A G
2 2
7
4
5
1
4
3
1
7
5
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
1
7
5
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
1
7
5
4
4
4
3 - Aplicações de Modelos de Redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 5
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
6a inclusão de arco
Árvore de Cobertura Mínima 
Solução do Algoritmo de Kruskal – (III)
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
B
D
C
F
E
A G
2 2
7
4
5
1
4
3
4
1
7
5
Observação: 
A árvore de cobertura 
mínima obtida com o 
algoritmo de Kruskal
é idêntica a obtida 
com o algoritmo anterior 
de Prim.
3 - Aplicações de Modelos de Redes
Não pode ser incluído pois 
fecha um ciclo
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Árvore de Cobertura Mínima 
Algoritmo de Kruskal 
3 - Aplicações de Modelos de Redes
Pseudo Código
E(1) is the set of the sides of the minimum genetic tree. 
E(2) is the set of the remaining sides. 
STEPS 
E(1)=0,E(2)=E 
While E(1) contains less then n-1 sides and E(2)=0 do 
From the sides of E(2) choose one with minimum cost-->e(ij) 
E(2)=E(2)-{e(ij) } 
If V(i),V(j) do not belong in the same tree then 
unite the trees of V(i) and V(j) to one tree. 
end (If) 
end (While) 
End Of Algorithm. 
Solver: http://students.ceid.upatras.gr/~papagel/project/kruskal.htm
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Caminho Mais Curto em uma Rede
Definição
Goldbarg e Luna, 2000
Sendo u e v dois nós do Grafo (N,A), o caminho mais curto entre u e v é 
uma seqüência de arcos que, passando por nós distintos, liga u a v de 
forma a acumular a menor distância. 
Para que possa haver um caminho mais curto entre os nós u
e v é indispensável que exista primeiramente uma conexão
entre u e v, ou seja, se existe um caminho de u para v, 
significa que o v é sucessor de u em algum passeio sobre o 
conjunto N.
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG1529- Distribuição Física
Prof: Rogério Lopes
O encarregado da distribuição de um determinado produto precisa manter 
abastecido o armazém que fica no lado oposto da cidade. A rede pela qual se 
deve fazer o percurso está apresentada na figura abaixo. 
Caminho Mais Curto em uma Rede
Exemplo de Aplicação – Distribuição de Produtos
O nó 1 representa o lugar de partida (origem) e o nó 7 é o armazém de destino. Deve-se 
determinar a melhor trajetória que minimize a distância total percorrida de 1 a 7.
2 5
1 7
3 6
4
2 5
11 810
4 1
9
6
73
Gutierez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 6
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Caminho Mais Curto em uma Rede
Algoritmo de Dijkstra – (I)
No Método de Dijkstra, para redes com arcos positivos (distâncias), os 
nós ganham “rótulos” temporários (T) ou permanentes (P). Um rótulo é 
definido como permanente quando nele se achou a distância mais curta 
para o nó 1. 
* n é o número total de nós na rede
Gutierez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez adaptado de Pizzolato, 2003
Passo 0: Iniciar u1 = 0 (distância do nó origem ao próprio nó origem)
Sejam os conjuntos P e T tal que P = {1} e T = {2,3,...n}, onde n é o número total de nós na rede.
Passo 1: Escolha um rótulo permanente: Achar o nó k Є T (apenas para os temporários sucessores 
ao nó 1) tal que uk = min (uj}. Sendo uj a distância do nó 1 aos seus seguintes próximos nós.
Adicionar o nó k ao conjunto dos nós permanentes e retira-lo do conjunto dos nós temporários.
Passo 2: Revisão dos rótulos temporários, que podem virar permanentes. Fórmula geral para o 
cálculo de uk:
uk = mini (distância mais curta entre o nó 1 e o nó permanente j precedente ao nó i + 
distância entre o atual nó i e seu predecessor j) = mini (uj + dji)
Válido para todo nó i pertencente a T que tem como predecessor um nó permanente. Fazer para 
todos os possíveis j de cada i (caso em que i tem mais de um nó permanente como predecessor).
O menor i vai virar rótulo permanente.
Adicionar o nó k ao conjunto dos nós permanentes e retira-lo do conjunto dos nós temporários.
Retorne ao início do Passo 2 até que o último uj seja encontrado, ou seja, T = Ø.
A fórmula faz com que a distância mais curta uj ao nó j somente possa ser calculada depois de se 
conhecer a distância mais curta a cada nó predecessor i, ligado a j por meio de um arco.
3 - Aplicações de Modelos de Redes
Caminho Mais Curto em uma Rede
Algoritmo de Dijkstra – (II)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (I)
Passo 0: u1 = 0
P = {1} e T={2,3,4,5,6,7}
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
Gutierez adaptado de Pizzolato, 2003
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Passo 1:
uk = mini (u1 + d12, u1 + d14, u1 + d13) => demais nós não são considerados
pois dentre os seus antecessores não existem nós permanentes
uk = mini (0 + 2, 0 + 10, 0 + 4)
=> uk (k=2) = 2
temos u2 = 2
T = {3,4,5,6,7}
P={1,2} (Sombreado)
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
i = 2 i = 4 i = 3
3 - Aplicações de Modelos de Redes
j sempre = 1
Gutierez adaptado de Pizzolato, 2003
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (II)
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 7
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
Passo 2:
Quem pode virar permanente?
3 - Aplicações de Modelos de Redes
Gutierez adaptado de Pizzolato, 2003
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (III)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Passo 2:
uk = mini (u1 + d13, u1 + d14, u2 + d24, u2 + d25) 
=> demais nós não são considerados pois dentre os seus antecessores não existem nós 
permanentes
uk = mini (0 + 4, 0 + 10, 2 + 11, 2 + 5) 
=> uk (k=3) = 4 
temos u3 = 4
T = {4,5,6,7}
P={1,2,3} (Sombreado)
Ainda existem nós temporários.
i=3 e j=1 i=4 e j=1 i=4 e j=2 i=5 e j=2
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
u3=4
3 - Aplicações de Modelos de Redes
Gutierez adaptado de Pizzolato, 2003
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (IV)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Passo 2:
Quem pode virar permanente?
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
u3=4
3 - Aplicações de Modelos de Redes
Gutierez adaptado de Pizzolato, 2003
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (V)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
u3=4
u4=7
Deve-se continuar até não existirem mais nós temporários
T = {4, 5,7} P={1,2,3,6} (Sombreado) T = {7} P={1,2,3,4,5,6} (Sombreado)
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
u3=4
u4=7
u5=7
u6=5
2
4
3
5
6
1 7
2
9
5
4
10
11
3
1
6
7
8
u1=0
u2=2
u3=4
u4=7
u5=7
u6=5
u7=13
T = {Ø} P={1,2,3,4,5,6,7} (Sombreado)
Como T = Ø significa que todos os nós 
estão rotulados e chegamos à solução 
final. A mínima distância do nó 1 ao nó 7 
é 13 e segue o caminho: 1 – 2 – 5 – 7 . 
u6=5
4
6
3 - Aplicações de Modelos de Redes
Gutierez adaptado de Pizzolato, 2003
Caminho Mais Curto em uma Rede
Solução do Algoritmo de Dijkstra – (VI)
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 8
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Caminho Mais Curto Entre Todos os Pares de Nós
Gutierez baseado em Larson & Odoni, 1981
Extensão do problema de encontrar o caminho mais curto entre um nóorigem e um nó destino, resolvido com o algoritmo de Dijskstra.
O objetivo não é só encontrar o caminho mais curto que ligue um nó
específico aos demais da rede e sim conhecer qual a menor distância
entre qualquer par de nós da rede.
Alternativas de Solução:
� Repetir o Algoritmo de Dijkstra sucessivas vezes alternando as 
origens.
� Empregar o Algoritmo de Floyd.
3 - Aplicações de Modelos de Redes
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (I)
Gutierez baseado em Larson & Odoni, 1981
Deseja-se encontrar o caminho mais curto entre todos os pares de nós 
da rede da figura abaixo. 
3 - Aplicações de Modelos de Redes
1
2
3
4 5
4
3
8
1
2
4
1
2
6
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Inicia-se este algoritmo numerando os “n” nós da rede com inteiros 
positivos 1,2,...,n e, a seguir, construindo as matrizes de Distância -
D(0) e de Precedência - P(0), que serão preenchidas com os 
elementos:
d(i,j) se o arco(i,j) existe
D0(i,j) = 0 se i = j
∞ se o arco (i,j) não existe
P0(i,j) = i para i≠j
-- (branco) para i=j.
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (II)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
1
2
3
4 5
4
3
8
1
2
4
1
2
6
1 2 3 4 5
1 0 3
2 4 0 1 2
D(0) = 3 3 8 2 6
4 1 0 4
5 1 6 4 0
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
0
Matriz de Distância
1 2 3 4 5
1 --- 1 1 1 1
2 2 --- 2 2 2
P(0) = 3 3 3 --- 3 3
4 4 4 4 --- 4
5 5 5 5 5 ---i
j
Matriz de Precedência
Construção das Matrizes
3 - Aplicações de Modelos de Redes
No exemplo sinalizamos, a cada passo, com “+” os elementos da matriz de distância que são
atualizados. Somente os respectivos elementos na matriz de precedência é que sofrem atualização.
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (III)
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 9
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Passo 1: Faça k=1
Passo 2: Obtenha todos os elementos da Matriz atualizada de Distâncias D(k) 
por meio da seguinte relação:
Passo 3: Obtenha todos os elementos da Matriz atualizada de Precedência 
P(k) da seguinte maneira:
se
em outros casos
Passo 4: Se k=n, pare; 
Se k<n, faça k=k+1 e volte para o Passo 2.
[ ]j)(k,dk)(i,dj),(i,dMinj)(i,d 1k1k1kk −−− +=
),(),( 1 jkpjip kk −=
),(),( 1 jipjip kk −=
),(),( 1 jidjid kk −<
3 - Aplicações de Modelos de Redes
No exemplo sinalizamos, a cada passo, com um “*” a respectiva linha e coluna k. Essas linhas e
colunas são conhecidas a priori e não requerem nenhuma mudança e, sendo assim, podem ser
copiadas da respectiva matriz do passo anterior.
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (IV)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Através do Nó 1 (k=1)
1* 2 3 4 5 1* 2 3 4 5
*1 0 3 *1 --- 1 1 1 1
2 4 0 7+ 1 2 2 2 --- 1+ 2 2
D(1) = 3 3 8 0 2 6 P(1) = 3 3 3 --- 3 3
4 1 0 4 4 4 4 4 --- 4
5 1 6 4 0 5 5 5 5 5 ---
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
1 2 3 4 5 1 2 3 4 5
1 0 3 1 --- 1 1 1 1
2 4 0 1 2 2 2 --- 2 2 2
D(0) = 3 3 8 2 6 P(0) = 3 3 3 --- 3 3
4 1 0 4 4 4 4 4 --- 4
5 1 6 4 0 5 5 5 5 5 ---
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
0
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (V)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Através do Nó 1 (k=1)
1 2 3 4 5 1 2 3 4 5
1 0 3 1 --- 1 1 1 1
2 4 0 7 1 2 2 2 --- 1 2 2
D(1) = 3 3 8 0 2 6 P(1) = 3 3 3 --- 3 3
4 1 0 4 4 4 4 4 --- 4
5 1 6 4 0 5 5 5 5 5 ---
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
∞∞∞∞
∞∞∞∞
∞∞∞∞
Através do Nó 2 (k=2)
1 2* 3 4 5 1 2* 3 4 5
1 0 3 1 --- 1 1 1 1
*2 4 0 7 1 2 *2 2 --- 1 2 2
D(2) = 3 3 8 0 2 6 P(2) = 3 3 3 --- 3 3
4 5+ 1 8+ 0 3+ 4 2+ 4 1+ --- 2+
5 5+ 1 6 2+ 0 5 2+ 5 5 2+ ---
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (VI)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Através do Nó 2 (k=2)
1 2 3 4 5 1 2 3 4 5
1 0 3 1 --- 1 1 1 1
2 4 0 7 1 2 2 2 --- 1 2 2
D(2) = 3 3 8 0 2 6 P(2) = 3 3 3 --- 3 3
4 5 1 8 0 3 4 2 4 1 --- 2
5 5 1 6 2 0 5 2 5 5 2 ---
1 2 3* 4 5 1 2 3* 4 5
1 0 11+ 3 5+ 9+ 1 --- 3+ 1 3+ 3+
2 4 0 7 1 2 2 2 --- 1 2 2
D(3) = *3 3 8 0 2 6 P(3) = *3 3 3 --- 3 3
4 5 1 8 0 3 4 2 4 1 --- 2
5 5 1 6 2 0 5 2 5 5 2 ---
∞∞∞∞ ∞∞∞∞ ∞∞∞∞
Através do Nó 3 (k=3)
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (VII)
Departamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia IndustrialDepartamento de Engenharia Industrial
ENG 1529 ENG 1529 ENG 1529 ENG 1529 ---- Distribuição FísicaDistribuição FísicaDistribuição FísicaDistribuição Física
Professor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P LopesProfessor: Rogério G. P Lopes
Página: 10
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
1 2 3 4 5 1 2 3 4 5
1 0 11 3 5 9 1 --- 3 1 3 3
2 4 0 7 1 2 2 2 --- 1 2 2
D(3) = 3 3 8 0 2 6 P(3) = 3 3 3 --- 3 3
4 5 1 8 0 3 4 2 4 1 --- 2
5 5 1 6 2 0 5 2 5 5 2 ---
Através do Nó 4 (k=4)
1 2 3 4* 5 1 2 3 4* 5
1 0 6+ 3 5 8+ 1 --- 4+ 1 3 2+
2 4 0 7 1 2 2 2 --- 1 2 2
D(4) = 3 3 3+ 0 2 5+ P(4) = 3 3 4+ --- 3 2+
*4 5 1 8 0 3 *4 2 4 1 --- 2
5 5 1 6 2 0 5 2 5 5 2 ---
Através do Nó 3 (k=3)
Gutierez baseado em Larson & Odoni, 1981
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (VIII)
Departamento de Engenharia Industrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Através do Nó 4 (k=4)
1 2 3 4 5 1 2 3 4 5
1 0 6 3 5 8 1 --- 4 1 3 2
2 4 0 7 1 2 2 2 --- 1 2 2
D(4) = 3 3 3 0 2 5 P(4) = 3 3 4 --- 3 2
4 5 1 8 0 3 4 2 4 1 --- 2
5 5 1 6 2 0 5 2 5 5 2 ---
Através do Nó 5 (k=5)
1 2 3 4 5 * 1 2 3 4 5*
1 0 6 3 5 8 1 --- 4 1 3 2
2 4 0 7 1 2 2 2 --- 1 2 2
D(5) = 3 3 3 0 2 5 P(5) = 3 3 4 --- 3 2
4 5 1 8 0 3 4* 2 4 1 --- 2
*5 5 1 6 2 0 5 2 5 5 2 ---
PASSO 3: Como k = n = 5, o procedimento termina.
Gutierez baseado em Larson & Odoni, 1981
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (IX)
Departamento de EngenhariaIndustrial
IND 1607 - Distribuição Física
Prof: Rogério Lopes
Departamento de Engenharia Industrial
ENG 1529- Distribuição Física
Prof: Rogério Lopes
Gutierez baseado em Larson & Odoni, 1981
Por exemplo, a distância mais curta entre os nós 1 e 5 tem um comprimento de
d5(1,5) = 8 unidades e o caminho mais curto passa através dos nós {1,3,4,2,5}.
Observa-se que no último passo D(5) não se pode melhorar nada em relação ao
anterior D(4). Portanto, as Matrizes finais D(5) e P(5) indicam o caminho mais
curto entre todos os pares de nós.
No exemplo, determina-se o caminho da seguinte maneira:
Tomando-se p5(1,5), este indica que o nó 5 tem como predecessor o nó 2 no
caminho 1 – 5. O elemento p5(1,2) indica que o nó 2 tem como predecessor o nó 4
no caminho 1 – 2. O elemento p5(1,4) indica que o nó 4 tem como predecessor o
nó 3 no caminho 1 – 4. O elemento p5(1,3) indica que o nó 3 tem como
predecessor o nó 1 no caminho 1 – 3.
Voltamos até o nó 1, que é o nó que consideramos como início do caminho e,
desta forma, obtivemos o caminho mais curto entre os pares de nós.
3 - Aplicações de Modelos de Redes
Caminho Mais Curto Entre Todos os Pares de Nós
Aplicação do Algoritmo de Floyd (X)