Fórum de discussão

Oi Gabriel,

Muito bom você ter perguntado!

Sobre a questão do guloso, eu ainda não entendi por que não funciona

Antes de mais nada temos que ver se estamos falando do mesmo algoritmo guloso.
A denominação algoritmo guloso é muitas vezes usada para paradigmas diferentes de algoritmos.

Digamos que um algoritmo guloso é um algoritmo que não se arrepende de suas decisões.
No caso do caminho mínimo de um determinado vértice origem s a um vértice destino t, o algoritmo é iterativo.
No início de cada iteração temos um caminho (como o algoritmo ativo na DFS).
No início da primeira iteração, o caminho é composto apenas do vértice origem s.
Cada iteração consiste em:

1. pegar o vértice v que é ponta final do caminho;
2. examinar todos os arcos v-w saindo do vértice v;
3. selecionar o vértice o arco v-w mais leve/curto/barato saindo de v;
4. inserir w no final do caminho;
5. começar nova iteração (com w no papel de v).

O algoritmo pára quando chegamos ao vértice destino t.

É isso que você está considerando como guloso?