Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDECAN 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg523010
Banca
IDECAN
Órgão
IF-PA
Ano
2025
Nível
Superior
Cargo
Professor - Informática
Durante o desenvolvimento de um sistema de planejamento de rotas para transporte público urbano, um professor do EBTT orientou seus alunos a analisar diferentes algoritmos clássicos de grafos com base em sua aplicabilidade e eficiência computacional. O sistema considera, além da distância, outros fatores como custo, tempo de deslocamento e subsídios tarifários, o que pode resultar em pesos negativos nas arestas do grafo. No entanto, não se admite a existência de ciclos com peso negativo, pois eles inviabilizariam o cálculo de rotas válidas. O sistema calcula as melhores rotas a partir de um ponto de origem único. Considerando esse contexto e o comportamento dos algoritmos em grafos ponderados, o melhor algoritmo para a aplicação é:
Ao algoritmo de Bellman-Ford é capaz de lidar com pesos negativos e detectar ciclos negativos em grafos direcionados.
Bo algoritmo de Dijkstra é eficiente em grafos ponderados com pesos não negativos para encontrar o caminho mínimo entre dois vértices.
Co algoritmo de Prim encontra o caminho mínimo entre dois vértices em um grafo ponderado e conexo.
Do algoritmo de Floyd-Warshall é utilizado para encontrar a árvore geradora mínima de um grafo não direcionado e ponderado.
Eo algoritmo de Kruskal é preferido em grafos direcionados para detecção de ciclos negativos.
Revelar gabarito e comentário▾
GabaritoA — o algoritmo de Bellman-Ford é capaz de lidar com pesos negativos e detectar ciclos negativos em grafos direcionados.
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 caminho mínimo em grafos ponderados
Gabarito: letra A. O algoritmo de Bellman-Ford é o único, entre os listados, capaz de lidar com pesos negativos nas arestas e de detectar ciclos negativos, o que atende exatamente aos requisitos do enunciado (pesos negativos admissíveis, mas ciclos negativos não).
O problema exige um algoritmo de caminho mínimo a partir de uma origem única (fonte única) em um grafo que pode conter pesos negativos, mas que não possui ciclos negativos. O algoritmo de Dijkstra, embora eficiente, falha na presença de pesos negativos. Já Bellman-Ford resolve o problema e ainda detecta ciclos negativos, atendendo perfeitamente à necessidade.
Alternativa A — ✅ Correta ⟵ GABARITO
O algoritmo de Bellman-Ford (também conhecido como Bellman-Ford-Moore) resolve o problema de caminhos mínimos de fonte única em grafos direcionados (ou não direcionados, mediante conversão) com pesos que podem ser negativos. Ele executa relaxamentos sucessivos em todas as arestas por |V|−1 iterações e, em uma iteração adicional, detecta ciclos negativos. Isso casa exatamente com o contexto: o sistema permite pesos negativos (ex.: subsídios) mas não admite ciclos negativos.
Alternativa B — ❌ Incorreta
O algoritmo de Dijkstra é de fato eficiente (O(E + V log V) com heap) para pesos não negativos. Contudo, ele falha na presença de pesos negativos, pois sua premissa de que os valores extraídos da fila de prioridades são monotonicamente crescentes é quebrada. Como o enunciado afirma que o grafo pode ter pesos negativos, Dijkstra não é o melhor algoritmo — embora seja uma afirmação verdadeira isoladamente, não atende ao contexto.
Alternativa C — ❌ Incorreta
O algoritmo de Prim é um algoritmo guloso para encontrar a árvore geradora mínima (MST) de um grafo conexo e ponderado, não o caminho mínimo entre dois vértices. Ele constrói uma árvore que conecta todos os vértices com o menor peso total, e não uma rota de origem a destino.
Alternativa D — ❌ Incorreta
O algoritmo de Floyd-Warshall resolve o problema de caminhos mínimos entre todos os pares de vértices (all-pairs shortest paths), e não a árvore geradora mínima. Além disso, trabalha com grafos direcionados ou não, mas não gera MST. A descrição na alternativa está trocada: a árvore geradora mínima é obtida por Prim ou Kruskal.
Alternativa E — ❌ Incorreta
O algoritmo de Kruskal é outro algoritmo para árvore geradora mínima em grafos não direcionados. Ele não é usado para detecção de ciclos negativos (essa função é do Bellman-Ford) e não se aplica a grafos direcionados diretamente. A afirmação é completamente equivocada.
PEGA ESSA DICA!
Para questões sobre caminho mínimo, identifique:
Se há pesos negativos → Bellman-Ford (ou Floyd-Warshall para todos os pares).
Se não há pesos negativos → Dijkstra (mais eficiente).
Se o objetivo é árvore geradora mínima → Prim ou Kruskal.