Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MG 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg240040
Banca
IF-MG
Órgão
IF-MG
Ano
2024
Nível
Superior
Cargo
PROFESSOR EBTT - Ciência da Computação e Sistemas de Informação. - Ribeirão das Neves
Considere um grafo não direcionado e ponderado, representado por G = (V,E), onde V é o conjunto de vértices e E é o conjunto de arestas com pesos positivos. Você precisa encontrar o caminho mais curto de um vértice s para todos os outros vértices do grafo. Qual dos seguintes algoritmos é mais eficiente para resolver esse problema, considerando que o grafo pode conter ciclos e as arestas possuem apenas pesos positivos?
  1. AO algoritmo de Floyd-Warshall, que tem complexidade O(n³), é o mais eficiente, pois calcula os caminhos mínimos entre todos os pares de vértices.
  2. BO algoritmo de Kruskal, que é ideal para encontrar a árvore geradora mínima, resolve eficientemente o problema dos caminhos mais curtos com complexidade O(E lg V).
  3. CO algoritmo de Bellman-Ford, com complexidade O(V E), é mais eficiente para resolver o problema de caminhos mínimos em grafos com pesos positivos, pois permite a presença de ciclos.
  4. DO algoritmo de Dijkstra, com complexidade O(E + V lg V), é o mais eficiente para grafos com pesos positivos, garantindo a solução dos caminhos mínimos a partir de um vértice s.
  5. EO algoritmo de Prim, com complexidade O(E lg V), é ideal para encontrar caminhos mínimos em grafos ponderados, garantindo a menor soma dos pesos das arestas.
Revelar gabarito e comentário

GabaritoD — O algoritmo de Dijkstra, com complexidade O(E + V lg V), é o mais eficiente para grafos com pesos positivos, garantindo a solução dos caminhos mínimos a partir de um vértice s.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Algoritmos de Caminhos Mínimos em Grafos com Pesos Positivos

Gabarito: letra D. O algoritmo de Dijkstra é o mais eficiente para encontrar o caminho mais curto de um vértice fonte a todos os demais em grafos com pesos positivos, com complexidade O(E + V log V) (usando heap de Fibonacci), enquanto os demais algoritmos apresentados ou são para problemas diferentes (árvore geradora mínima, todos os pares) ou têm pior desempenho (Bellman-Ford).

A questão cobra o conhecimento clássico sobre algoritmos de caminhos mínimos: Dijkstra para pesos não negativos, Bellman-Ford para pesos negativos (mas mais lento), Floyd-Warshall para todos os pares, e Kruskal/Prim para árvore geradora mínima.

Alternativa A — ❌ Incorreta

O algoritmo de Floyd-Warshall resolve o problema de caminhos mínimos entre todos os pares de vértices com complexidade O(V³). Para encontrar apenas a partir de uma única fonte, o Dijkstra é mais eficiente. Além disso, o enunciado pede o caminho mais curto de s para todos os outros, não entre todos os pares.

Alternativa B — ❌ Incorreta

O algoritmo de Kruskal encontra a árvore geradora mínima (MST), não caminhos mínimos. A MST minimiza a soma total dos pesos das arestas que conectam todos os vértices, mas não garante o menor caminho entre dois pontos específicos. O problema de caminho mínimo é diferente.

Alternativa C — ❌ Incorreta

O algoritmo de Bellman-Ford funciona com arestas de peso negativo e detecta ciclos negativos, mas sua complexidade O(VE) é maior que a de Dijkstra para grafos com pesos positivos. Como o grafo tem apenas pesos positivos, o Dijkstra é mais eficiente e suficiente.

Alternativa D — ✅ Correta ⟵ GABARITO

O algoritmo de Dijkstra é a escolha padrão para caminhos mínimos de fonte única em grafos com pesos não negativos. Com uma implementação usando heap de Fibonacci, sua complexidade é O(E + V log V), sendo mais rápido que Bellman-Ford e Floyd-Warshall para este caso. O fato de o grafo conter ciclos não é problema, desde que não haja arestas negativas (o que é garantido).

Alternativa E — ❌ Incorreta

O algoritmo de Prim também encontra a árvore geradora mínima, assim como Kruskal. Ele não resolve o problema de caminhos mínimos. Apesar de ter complexidade O(E log V) semelhante ao Dijkstra, o objetivo é diferente.

Gabarito: letra D

Link permanente: /questoes/qg240040