Logo Passei Direto
Buscar
Em um grafo nao ponderado, qual algoritmo pode ser utilizado para encontrar o caminho minimo?
a) Algoritmo de Dijkstra
b) Algoritmo de Bellman-Ford
c) Busca em Largura (BFS)
d) Algoritmo de Floyd-Warshall
User badge image
Questões para Estudantes

há 3 meses

Respostas

User badge image

Ed Verified user icon

há 3 meses

Para encontrar o caminho mínimo em um grafo não ponderado, a melhor abordagem é usar a Busca em Largura (BFS). Isso ocorre porque, em um grafo não ponderado, todos os arestas têm o mesmo peso (ou seja, podem ser consideradas como tendo peso 1), e a BFS explora todos os vértices a uma determinada distância antes de passar para a próxima. Vamos analisar as alternativas: a) Algoritmo de Dijkstra - Este algoritmo é ótimo para grafos ponderados, mas não é necessário para grafos não ponderados. b) Algoritmo de Bellman-Ford - Também é usado para grafos ponderados e não é a melhor escolha para grafos não ponderados. c) Busca em Largura (BFS) - Correto! É o algoritmo mais adequado para encontrar o caminho mínimo em um grafo não ponderado. d) Algoritmo de Floyd-Warshall - Este algoritmo é usado para encontrar caminhos mínimos entre todos os pares de vértices em grafos ponderados, não é específico para grafos não ponderados. Portanto, a alternativa correta é: c) Busca em Largura (BFS).

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Mais perguntas desse material

Mais conteúdos dessa disciplina