Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
cg020778
Banca
CESGRANRIO
Órgão
BNDES
Ano
2024
Nível
Superior
Cargo
Analista - Análise de Sistemas - Desenvolvimento (Manhã)
Determinada empresa venceu a licitação de uma secretaria de transportes municipal para a implementação de um software que faz o cálculo da melhor rota, dentre diversas possíveis, para que o ônibus da prefeitura ligue os pontos inicial e final da linha mais frequentada com distância percorrida mínima.Nesse contexto, o responsável pelo projeto resolveu utilizar um algoritmo consagrado de caminho mínimo, o algoritmo de
ABubblesort
BDijkstra
CFord-Fulkerson
DKruskal
EQuicksort
Revelar gabarito e comentário▾
GabaritoB — Dijkstra
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”.
Algoritmo de Caminho Mínimo
Gabarito: letra B. O problema descrito — encontrar a rota de distância mínima entre dois pontos em um grafo — é resolvido pelo algoritmo de Dijkstra, que é o algoritmo clássico e consagrado para caminhos mínimos em grafos com arestas de peso não negativo (como distâncias geográficas).
A questão testa o conhecimento básico sobre a finalidade de algoritmos clássicos. A chave é associar cada alternativa ao problema que ela resolve.
O Bubblesort é um algoritmo de ordenação, utilizado para rearranjar listas em ordem crescente ou decrescente. Não tem relação com cálculo de rotas ou caminhos.
Alternativa B — ✅ Correta ⟵ GABARITO
O algoritmo de Dijkstra é projetado exatamente para encontrar o caminho de menor custo (distância, tempo, etc.) entre um nó origem e todos os outros nós em um grafo com pesos não negativos. É a escolha natural para o problema de rota mínima descrito.
Alternativa C — ❌ Incorreta
O Ford-Fulkerson é um algoritmo para o problema do fluxo máximo em redes, utilizado para determinar o maior fluxo possível entre uma fonte e um sumidouro. Não se aplica a caminhos mínimos.
Alternativa D — ❌ Incorreta
O algoritmo de Kruskal é usado para encontrar a árvore geradora mínima (MST) de um grafo, conectando todos os vértices com o menor custo total, mas não resolve o caminho mínimo entre dois pontos específicos.
Alternativa E — ❌ Incorreta
O Quicksort é um algoritmo de ordenação eficiente, assim como o Bubblesort, sem aplicação em problemas de roteamento.
PEGA ESSA DICA!
Para provas de concurso, decore a finalidade de cada algoritmo clássico: Dijkstra → caminho mínimo; Kruskal/Prim → árvore geradora mínima; Ford-Fulkerson → fluxo máximo; Bubblesort/Quicksort/Mergesort → ordenação.