Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos nas arestas, qual condição sobre os pesos é necessária?
- A) Pesos negativos são permitidos, contanto que sejam balanceados entre arestas.
- B) A soma dos pesos deve ser positiva para que Dijkstra funcione.
- C) Dijkstra funciona apenas em grafos com arestas do mesmo peso.
- D) Todos os pesos das arestas devem ser não-negativos.
- E) Os pesos das arestas podem ser negativos, desde que não sejam maiores que zero.
✅ Resposta correta: alternativa D
Resolução passo a passo
- Resolvendo por conta própria, o algoritmo de Dijkstra calcula caminhos mínimos a partir de um vértice de origem, fixando em cada passo o vértice ainda não visitado com menor distância provisória e relaxando suas arestas de saída. Essa escolha gulosa só é definitiva se nenhuma aresta futura puder reduzir uma distância já fixada, o que exige que nenhum peso seja negativo. Passo 2: Por isso, a condição necessária é que todos os pesos das arestas sejam não-negativos (alternativa D). Passo 3: A alternativa A está errada porque pesos negativos quebram a garantia do algoritmo, mesmo que sejam compensados por outros pesos positivos, pois a ideia de balanceamento não elimina o problema. Passo 4: A alternativa B está errada porque o que importa é o sinal de cada peso individualmente, e não a soma total dos pesos do grafo ou de um caminho. Passo 5: A alternativa C está errada porque Dijkstra funciona com pesos diferentes entre as arestas; o requisito é sobre o sinal dos pesos, não sobre serem iguais. Passo 6: A alternativa E está errada porque permitir pesos negativos, desde que não sejam maiores que zero, ainda inclui valores negativos, que é justamente o que invalida o algoritmo. Passo 7: O gabarito oficial D está correto, sem divergência.
💡 Dica: Considere as propriedades dos pesos das arestas.
Alternativa por alternativa
O aluno acredita que pesos negativos são aceitos desde que haja compensação entre arestas, como se a soma global fosse o que importa.
Por que engana: Confundir a condição de que pesos negativos são permitidos, levando a resultados incorretos no cálculo de caminhos mínimos.
O aluno associa a validade do algoritmo à soma dos pesos, quando a condição depende do sinal de cada aresta individualmente.
O aluno confunde a exigência do algoritmo com a necessidade de pesos uniformes, imaginando que o grafo precisa ter arestas de mesmo peso.
Dijkstra assume que a relaxação de distâncias nunca reduzirá um caminho já extraído do heap; arestas com peso negativo podem invalidar essa ordem e produzir resultados incorretos.
O aluno entende que pesos negativos são tolerados enquanto não forem positivos, sem perceber que o zero e os valores negativos continuam violando a premissa de não-negatividade.
Raio-X da questão
algoritmo de Dijkstra
avaliacao
pesos em grafos · algoritmos de busca
Revisar as condições necessárias para o algoritmo de Dijkstra.
Confundir a condição de que pesos negativos são permitidos, levando a resultados incorretos no cálculo de caminhos mínimos.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Por que o algoritmo de Dijkstra não garante caminhos mínimos em um grafo que contém arestas com peso negativo?
- Em um grafo conexo com pesos nas arestas, qual propriedade caracteriza uma árvore geradora mínima (MST)?
- No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada para…
- Qual propriedade deve ter um grafo dirigido para que seja possível executar um algoritmo de ordenação topológica sobre…
- Em um algoritmo de Dijkstra implementado para um grafo ponderado com listas de adjacência, qual variável armazena a…
- Em uma competição de programação, uma equipe precisa calcular o menor custo para sair de um ponto inicial e chegar a…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog