10 johnson

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
10 de outubro de 2017
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 1 / 20
Conteúdo
1
Algoritmo de Johnson
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 2 / 20
Algoritmo de Johnson
Histórico
O algoritmo proposto por, Donald B. Johnson em 1977, determina os caminhos
mais curtos entre todos os pares de vértices em grafos:
i. Direcionados;
ii. Ponderados;
iii. Com arcos de peso negativo;
iv. Sem ciclos de peso negativo.
Tem boa aplicação computacional em grafos esparsos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 3 / 20
Algoritmo de Johnson
Princípio
i. O algoritmo de Johnson retorna uma matriz de pesos de caminhos mais curtos
ou informa que o grafo de entrada contém um ciclo de peso negativo;
ii. Subrotinas: algoritmos de Dijkstra e Bellman-Ford;
iii. Utiliza também uma técnica de reponderação para eliminar arcos de peso
negativo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 4 / 20
Algoritmo de Johnson
Reponderação
1) Se todos os pesos de arcos w em um grafo G = (V,E) são não negativos,
podemos encontrar caminhos mais curtos entre todos os pares de vértices exe-
cutando o algoritmo de Dijkstra uma vez a partir de cada vértice;
2) Se G possui arcos de peso negativo, mas nenhum ciclo de peso negativo, sim-
plesmente calculamos um novo conjunto de pesos de arcos não negativos que
nos permita aplicar o mesmo método;
3) O novo conjunto de pesos wˆ deve satisfazer a duas propriedades importantes:
i Para todos os pares de vértices u, v ∈ V , um caminho ρ é um caminho mais curto de u
até v usando a função de peso w se e somente se ρ também é um caminho mais curto
desde u até v usando a função de peso wˆ;
ii Para todos os arcos (u, v), o novo peso wˆ(u, v) é não negativo.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 5 / 20
Algoritmo de Johnson
Reponderação
1) O pré-processamento de G para determinar uma nova função de peso wˆ pode ser executado
em tempo proporcional ao número de nós e de arestas do grafo;
2) Para um grafo orientado ponderado G = (V,E) com a função de peso w : E → R, seja h :
V → R qualquer função que mapeia vértices para números reais. Para cada arco (u, v) ∈ E,
definimos
wˆ(u, v) = w(u, v) + h(u) = h(v)
3) A função wˆ(u, v) atende às duas propriedades postas anteriormente: consistência dos menores
caminhos e não negatividade;
4) Para a utilização da função definida anteriormente, um vértice artificial s, sem antecessores
e adjacente a todos os demais vértices usando arcos de peso zero, deve ser adicionado ao
grafo;
5) A função h(v) pode ser definida como o comprimento do caminho mais curto entre a origem
s e o vértice v (∀v ∈ V ), usando os pesos determinados por w;
6) É importante observar que o caminhos mais curtos citados acima podem conter arcos de peso
negativo, portanto, podem ser calculados pelo algoritmo de Bellman-Ford.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 6 / 20
Algoritmo de Johnson
Terminologia
w: pesos originais dos arcos do grafo;
wˆ: pesos reponderados dos arcos do grafo;
δ: comprimentos de caminhos mais curtos calculados usando w;
δˆ: comprimentos de caminhos mais curtos calculados usando wˆ;
G
′
= (V
′
, E
′
): Grafo criado a partir do grafo original, porém, com o acréscimo
do vértice s e respectivos arcos de peso zero;
D: Matriz de ordem n×n utilizada para armazenar os caminhos mais curtos.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 7 / 20
Algoritmo de Johnson
Entrada: Grafo G = (V,E)
1 G
′ ← G;
2 V
′ ← V ∪ {s};
3 E
′ ← E ∪ (s, v)∀v ∈ V ;
4 w(s, v)← 0∀v ∈ V ;
5 se Bellman-Ford(G
′
, w, s) = falso então
6 imprima "Contém Ciclo Negativo";
7 senão
8 para todo v ∈ V faça
9 h(v)← δ(s, v) //calculado por Bellman-Ford;
10 fim
11 fim
12 para todo (u, v) ∈ E′ faça
13 wˆ(u, v)← w(u, v) + h(u)− h(v);
14 fim
15 Crie uma matriz Dn×n;
16 para u ∈ V faça
17 Dijkstra(G, wˆ, u) //calcula δˆ(u, v), ∀v ∈ V ;
18 para v ∈ V faça
19 duv ← δˆ(u, v) + h(v)− h(u);
20 fim
21 fim
22 retorna D;
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 8 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 9 / 20
Exemplo
Grafo G
′
com a função peso w original. O novo vértice s é destacado em preto.
O rótulo de cada vértice v é h(v) = δ(s, v).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 10 / 20
Exemplo
Cada arco (u, v) é reponderado, utilizando o algoritmo de Bellman-Ford, com a
função peso wˆ(u, v) = w(u, v) + h(u)− h(v).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 11 / 20
Exemplo
i) Os slides a seguir ilustram a execução do algoritmo de Dijkstra em cada vértice
de G, usando a função de peso wˆ;
ii) Em cada figura, o vértice de origem é o destacado em preto, e os arcos som-
breados estão na árvore de caminhos mais curtos calculada pelo algoritmo;
iii) Dentro de cada vértice v estão indicados os valores δˆ(u, v) e δ(u, v), separados
por uma barra;
iv) O valor duv = δ(u, v) é igual a δˆ(u, v) + h(v)− h(u).
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 12 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 13 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 14 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 15 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 16 / 20
Exemplo
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 17 / 20
Exercício
Execute o algoritmo de Johnson para o grafo acima.
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 18 / 20
Dúvidas? Valar joll	oris
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 19 / 20
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);
Allexandre Fortes S. Reis (UFSJ) Otimização em Redes 10 de outubro de 2017 20 / 20
	Algoritmo de Johnson