BuscaGulosaGrafos

Busca Gulosa em Grafos
IF672 - Algoritmos e Estruturas de Dados
CIn - UFPE
Adriana Libório Fernandes Lins
Arthur Cavalcanti Alem
Átila Valgueiro Malta Moreira
Flavio Juvenal da Silva Júnior
Gustavo Cauê Silva Botelho
Matheus Bispo Arrais de Souza

Murilo Raphael de Souza Lira
Rafael Alberto Gomes Pereira Lima
Rafael Brandão Lobo
Rafael Loureiro de Carvalho
Tiago Carneiro Pessoa Canto
Vinicius Miranda Cesar

[e-mail]
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Busca Gulosa
A cada passo, é escolhida uma aresta segundo algum critério de prioridade (aresta com menor custo, menor caminho, etc) analisando um histórico das operações realizadas até então.
Por exemplo: sabendo o custo do caminho necessário para atingir o nó atual a partir de um nó inicial, escolher a aresta que irá proporcionar o menor caminho do nó atual para o próximo nó
(Algoritmo de Dijkstra).

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Dijkstra
Algoritmo capaz de descobrir o menor caminho existente entre um nó de origem e um nó de destino. É um algoritmo completo (caso exista o menor caminho entre os nós de origem e destino, o algoritmo sempre* encontra o menor caminho), ótimo (não há nenhum caminho menor do que o encontrado) e eficiente.
* O algoritmo de Dijkstra não é capaz de lidar com arestas de peso negativo.
Applet
© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Dijkstra
Qual é o menor caminho entre A e D?

0

A
5
C
∞

5
11

4

Fila de Prioridades

∞

B
5
D
∞

Comentários (cor)
- Nó ainda não visitado: azul
- Nó que está sendo visitado no momento: vermelho
- Nó visitado: preto

© Copyright 2003 Algoritmos e Estruturas de Dados - Todos os direitos reservados

Dijkstra
Qual é o menor caminho entre A e D?

0

A
5
C
∞

5
11

4

Fila de Prioridades
(A-A,0)

∞

B
5
D

Comentários
- Inserir o caso base no heap.
- Altera o menor caminho conhecido para A.

∞

© Copyright 2003