Caminhos Mínimos em Grafos

Prévia do material em texto

Teoria dos Grafos – 60 horas
Prof: Juliano Ratusznei.
Email: juliano.ratusznei@unicid.edu.br
Plano de ensino
Caminhos Mínimos
- Conceitos gerais;- Algoritmo de Djikstra;- Algoritmo de Bellman-Ford;- Caminhos mínimos entre todos os vértices.
Caminhos mínimos em Grafos
Considere um grafo orientado ponderado G = (V,E) em que cada aresta possui um rótulo não negativo associado que define o custo da aresta, e um dos vértices é especificado como origem. 
O problema é determinar quais são os caminhos mais curtos do vértice origem para cada um dos demais vértices em V e os seus custos. 
O caminho mais curto ou mínimo é definido pelo o caminho cuja soma dos custos dos vértices encontrados no caminho é mínimo. 
Caminhos mínimos em Grafos
O Algoritmo de Bellman-Ford é um algoritmo de busca de caminho mínimo em um dígrafo ponderado, ou seja, cujas arestas têm peso, inclusive negativo. 
Já o Algoritmo de Dijkstra resolve o mesmo problema, num tempo menor, porém exige que todas as arestas tenham pesos positivos
Caminhos mínimos em Grafos
O algoritmo de Dijkstra assume que todos os pesos de arestas no grafo de entrada são não negativos ele é ideal para aplicação em mapas rodoviários e aplicado na prática em sistemas comerciais;
O algoritmo de Bellman-Ford permite a existência de arestas de peso negativo, e produz a resposta correta vantagem não entra em loop infinito.
Bellman-Ford
Aplicação: 
Uma variação distribuída deste algoritmo é usada na área de redes de computadores; 
Seu objetivo é fornecer informação para cada host que deseja enviar pacotes (criar tabelas de encaminhamento – vetor de distância);
Calcula por qual saída ele deve enviar um pacote de modo que o mesmo chegue rapidamente ao destinatário;
Na área de redes de computadores devemos tomar cuidado com os “caminhos mais curtos”, ou os “caminhos de maior vazão” pois podemos congestionar a toda a rede se, na execução do algoritmo um host se tornar o “gargalo” da rede.
Sobre o algoritmo em : https://www.ime.usp.br/~pf/algoritmos_para_grafos/aulas/bellman-ford.html
Caminhos mínimos em Grafos
O algoritmo de Dijkstra permite encontrar o menor caminho entre um nó origem para todos os outros vértices do grafo
Cria uma árvore de percurso mínimo
Exemplo de grafo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Caminhos mínimos em Grafos
Entendendo o algoritmo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Teoria dos Grafos – Representações
Exercícios 1:
Implemente o Algoritmo de Djikstra em Linguagem C. Tempo estimado 1,5 aulas.
BUSCA EM LARGURA ALGORTIMO DE INUNDAÇÃO OU BRODCASTING
O algoritmo de inundação permite encontrar uma sequencia lógica de visitação dos vértices sem que haja repetição de vertices
Cria um vetor de vértices ordenado pela
ordem de visitação não considera os pesos
Exemplo de grafo
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
BUSCA EM LARGURA ALGORTIMO DE INUNDAÇÃO OU BRODCASTING
Exemplo de grafo visitação a partir do vértice 4
vetorInundação = [4, 3, 5, 0, 1, 2, 6]
Exemplo visitação a partir do vértice 2
vetorInundação = [2, 0, 5, 1, 3, 4, 6]
Exemplo visitação a partir do vértice 6
vetorInundação = [6, 5, 1, 2, 3, 4, 0]
0
1
3
2
4
5
6
6
1
4
2
3
4
3
2
11
9
Fim aula 7
Caminhos Mínimos
- Conceitos gerais;- Algoritmo de Djikstra;- Algoritmo de Bellman-Ford;- Caminhos mínimos entre todos os vértices.
image2.png
image3.png
image4.png