Algoritmo de Prim

Prévia do material em texto

Monitoria de Algoritmos
Algoritmo de Prim13
Algoritmo de Prim
◇ O algoritmo de Prim é um algoritmo guloso (greedy algorithm) empregado para 
encontrar uma árvore geradora mínima (minimal spanning tree) num grafo simples 
conexo ponderado. Isso significa que o algoritmo encontra um subgrafo do grafo 
original no qual a soma total das arestas é minimizada e todos os vértices estão 
interligados.
◇ Outros algoritmos conhecidos para encontrar árvores geradoras mínimas são o 
algoritmo de Kruskal e algoritmo de Boruvka. No entanto estes algoritmos podem 
ser empregados em grafos desconexos, enquanto o algoritmo de Prim precisa de 
um grafo conexo.
Algoritmo de Prim
https://youtu.be/cplfcGZmX7I
Algoritmo de Kruskal
https://youtu.be/71UQH7Pr9kU
Algoritmo de Bellman-Ford14
Algoritmo de Bellman-Ford
◇ O Algoritmo de Bellman-Ford é um algoritmo de 
busca de caminho mínimo em um grafo ponderado, 
ou seja, cujas arestas têm peso, inclusive negativo. 
O Algoritmo de Dijkstra resolve o mesmo problema, 
num tempo menor, porém exige que todas as 
arestas tenham pesos positivos. Portanto, o 
algoritmo de Bellman-Ford é normalmente usado 
apenas quando existem arestas de peso negativo.
Algoritmo de Bellman-Ford
https://youtu.be/9PHkk0UavIM
Algoritmo de Bellman-Ford
https://youtu.be/obWXjtg0L64