Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNDATEC 2023

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq893850
Banca
FUNDATEC
Órgão
IF-RS
Ano
2023
Nível
Superior
Cargo
Professor - Informática: Programação, Estrutura de Dados e Análise de Algoritimos
Assinale a alternativa correta sobre o funcionamento do algoritmo de Dijkstra, um algoritmo de caminho mínimo usado em grafos.
  1. AVértice inicial e, em seguida, explora apenas os vizinhos principais apenas, diminuindo o custo para alcançar cada um deles.
  2. BInicia com vários vértices, depois, explora cada um dos vizinhos, atualizando o custo por etapas para alcançar cada um.
  3. CVértice inicial e, em seguida, explora todos os seus vizinhos, atualizando o custo para alcançar cada um deles.
  4. DInicia com vários vértices, explora todos os vizinhos da esquerda e depois os da direita, atualizando o custo para alcançar por sequência.
  5. EDois vértices iniciais, em seguida, não explora os vizinhos, mas calcula diminuindo o custo para alcançar cada um deles.
Revelar gabarito e comentário

GabaritoC — Vértice inicial e, em seguida, explora todos os seus vizinhos, atualizando o custo para alcançar cada um deles.

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 Dijkstra

Gabarito: letra C. O algoritmo de Dijkstra é um algoritmo de caminho mínimo de fonte única para grafos com pesos não negativos. Ele parte de um único vértice inicial (fonte) e, a cada iteração, explora todos os vizinhos do vértice atual, atualizando as distâncias mínimas conhecidas para esses vizinhos, utilizando uma fila de prioridades para selecionar o vértice com menor distância ainda não processado. A alternativa C descreve exatamente esse comportamento: "Vértice inicial e, em seguida, explora todos os seus vizinhos, atualizando o custo para alcançar cada um deles."

  1. 1Vértice inicial (fonte única)
  2. 2Explora todos os vizinhos
  3. 3Atualiza distâncias mínimas
  4. 4Fila de prioridade seleciona menor distância
  5. 5Repete até processar todos os vértices
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que o algoritmo "explora apenas os vizinhos principais apenas" — o termo "apenas" restringe a exploração a um subconjunto, mas o algoritmo de Dijkstra explora todos os vizinhos do vértice atual, sem exceção. Além disso, a expressão "vizinhos principais" não é um conceito do algoritmo.

Alternativa B — ❌ Incorreta

Diz que o algoritmo "inicia com vários vértices". O algoritmo de Dijkstra é de fonte única: parte de um único vértice inicial. Não há inicialização com múltiplos vértices.

Alternativa C — ✅ Correta ⟵ GABARITO

Conforme explicado, descreve corretamente o funcionamento: inicia com um vértice fonte, explora todos os seus vizinhos e atualiza as distâncias. Essa é a essência do algoritmo.

Alternativa D — ❌ Incorreta

Afirma que o algoritmo "inicia com vários vértices" (erro) e que explora "vizinhos da esquerda e depois os da direita", o que não corresponde à lógica do Dijkstra, que não tem ordenação espacial desse tipo.

Alternativa E — ❌ Incorreta

Menciona "dois vértices iniciais" (erro, é apenas um) e que "não explora os vizinhos, mas calcula diminuindo o custo" — o algoritmo explora sim os vizinhos; o cálculo de custo é feito durante a exploração.

Gabarito: letra C.

Link permanente: /questoes/qq893850