Questão de Algoritmos e Estrutura de Dados — Estrutura de Dados — IBADE 2025
Algoritmos e Estrutura de Dados›Estrutura de Dados
Código
qg510109
Banca
IBADE
Órgão
Prefeitura de Castelo - ES
Ano
2025
Nível
Superior
Cargo
Analista de Sistemas
Em algoritmos para grafos direcionados com pesos, a escolha do método afeta corretude e custo. Assinale a alternativa que casa cenário e algoritmo de forma apropriada para caminhos mínimos de uma origem.
AEmpregar Dijkstra com fila de prioridade em grafo com pesos negativos e muitos ciclos, garantindo relaxamentos corretos em todo o espaço de busca.
BAplicar busca em largura com camadas em grafo ponderado denso, explorando estrutura uniforme de pesos para alcançar ótimo geral.
CUtilizar Bellman-Ford com relaxamentos por arestas repetidos por |V|−1 iterações, detectando ciclos com soma negativa por checagem adicional.
DRodar Floyd-Warshall para origem única esparsa de grande escala, priorizando simplicidade e cubo de tempo como estratégia base.
EExecutar Dantzig com emparelhamentos perfeitos para obter caminhos mínimos, explorando propriedades de custo marginal em cada passo.
Revelar gabarito e comentário▾
GabaritoC — Utilizar Bellman-Ford com relaxamentos por arestas repetidos por |V|−1 iterações, detectando ciclos com soma negativa por checagem adicional.
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 de Fonte Única
Gabarito: letra C. No cenário de grafos direcionados com pesos (inclusive negativos) e necessidade de detecção de ciclos de peso negativo, o algoritmo de Bellman-Ford é o mais apropriado: ele realiza relaxamentos por arestas repetidos por |V|-1 iterações e, após esse processo, executa uma verificação adicional para detectar ciclos com soma negativa. As demais alternativas apresentam incompatibilidades entre cenário e algoritmo.
A questão exige o conhecimento das propriedades fundamentais dos algoritmos clássicos de caminhos mínimos: Dijkstra (não tolera pesos negativos), Bellman-Ford (tolera pesos negativos e detecta ciclos negativos), Floyd-Warshall (para todos os pares, não fonte única), BFS (apenas grafos não ponderados) e Dantzig (não é um algoritmo de caminhos mínimos padrão).
Algoritmo
Cenário Adequado
Característica Principal
Limitação / Incompatibilidade
Dijkstra (com fila de prioridade)
Grafos com pesos não negativos
Relaxamento guloso; vértice com menor distância é finalizado
❌ Falha com pesos negativos; não detecta ciclos negativos
Busca em Largura (BFS)
Grafos não ponderados (pesos iguais/unitários)
Exploração por camadas; caminho mínimo = menor número de arestas
❌ Em grafos ponderados, não garante caminho de menor peso total
Bellman-Ford
Grafos com pesos negativos (ou não); detecta ciclos negativos
Relaxamentos repetidos por |V|−1 iterações + verificação extra
✅ Tolerante a pesos negativos; detecta ciclos de soma negativa
Floyd-Warshall
Todos os pares de vértices (não fonte única)
Programação dinâmica; complexidade O(V³)
❌ Ineficiente para fonte única em grafos esparsos
Dantzig
Não é algoritmo padrão de caminhos mínimos
Baseado em emparelhamentos e custo marginal
❌ Não se aplica ao problema de caminhos mínimos de fonte única
Caminhos mínimos (fonte única): Dijkstra (Peso negativo → falha, Fila de prioridade); Bellman-Ford (Peso negativo, Detecta ciclo negativo, |V|-1 iterações + checagem); BFS (Peso variado → falha, Peso uniforme); Floyd-Warshall (Fonte única → inadequado, Todos os pares)
Alternativa A — ❌ Incorreta
O algoritmo de Dijkstra, mesmo com fila de prioridade, não funciona corretamente em grafos com arestas de peso negativo. A presença de pesos negativos pode levar a relaxamentos incorretos, pois o algoritmo assume que uma vez extraído o vértice com menor distância, essa distância é definitiva. Ciclos negativos tornam o problema ainda mais complexo, e Dijkstra não os detecta.
Alternativa B — ❌ Incorreta
A busca em largura (BFS) explora o grafo em camadas e só produz caminhos mínimos quando todas as arestas têm o mesmo peso (ou peso unitário). Em um grafo ponderado com pesos variados, o caminho com menor número de arestas (descoberto pela BFS) não é necessariamente o de menor peso total. Portanto, não alcança o ótimo geral.
Alternativa C — ✅ Correta ⟵ GABARITO
O algoritmo de Bellman-Ford é projetado exatamente para o problema de caminhos mínimos de fonte única em grafos que podem conter arestas de peso negativo. Ele executa |V|-1 iterações de relaxamento sobre todas as arestas (garantindo convergência na ausência de ciclos negativos) e, em seguida, realiza uma iteração extra para verificar se ainda é possível relaxar alguma aresta — o que indicaria a presença de um ciclo de peso negativo. Essa descrição corresponde fielmente à alternativa.
Alternativa D — ❌ Incorreta
O algoritmo de Floyd-Warshall resolve o problema de caminhos mínimos entre todos os pares de vértices, não de fonte única. Além disso, sua complexidade é O(V³), o que o torna inadequado para grafos esparsos de grande escala quando se deseja apenas uma origem. Para fonte única em grafos esparsos, algoritmos como Dijkstra (com heap) ou Bellman-Ford são mais eficientes.
Alternativa E — ❌ Incorreta
O algoritmo de Dantzig (ou método simplex para fluxos em rede) não é um algoritmo de caminhos mínimos no sentido tradicional. A referência a "emparelhamentos perfeitos" e "custo marginal" sugere confusão com outros problemas (como o problema do caixeiro-viajante ou fluxo de custo mínimo). Não há um algoritmo clássico de caminhos mínimos de fonte única com esse nome.
Conclusão: O gabarito é a letra C. Bellman-Ford é a escolha correta para grafos com pesos negativos e necessidade de detecção de ciclos negativos, enquanto as demais opções associam equivocadamente algoritmos a cenários incompatíveis.