Por que o algoritmo de Dijkstra não garante caminhos mínimos em um grafo que contém arestas com peso negativo?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar as principais formas de organizar e representar a informação de maneira estruturada (matrizes, registros, listas e grafos) ou não estruturada (números, palavras, valores verdade).
Fonte: Base Nacional Comum Curricular (MEC).Questão
Por que o algoritmo de Dijkstra não garante caminhos mínimos em um grafo que contém arestas com peso negativo?
- A) Porque Dijkstra requer pesos não negativos; arestas negativas podem invalidar sua escolha gulosa do vértice com menor distância.
- B) O algoritmo Dijkstra assume que o grafo contém apenas ciclos positivos.
- C) Dijkstra funciona bem com pesagens negativas, mas não com pesos zero.
- D) Caminhos não mínimos podem ser garantidos com o uso de Dijkstra em grafos direcionais.
- E) Arestas negativas estimulam a escolha do vértice com maior distância.
✅ Resposta correta: alternativa A
Resolução passo a passo
- O algoritmo de Dijkstra é guloso: a cada iteração, escolhe o vértice ainda não fixado com menor distância provisória e o considera definitivo, pois supõe que nenhum caminho futuro poderá ser mais curto.
- Essa suposição só vale se todos os pesos forem não negativos. Se existe uma aresta com peso negativo, um caminho que passa por vértices ainda não visitados pode, ao final, somar um valor menor do que o vértice já fixado, mas o algoritmo já o considerou definitivo.
- Assim, a alternativa A está correta e coincide com o gabarito oficial: a exigência de pesos não negativos é o motivo da falha, e a escolha gulosa do menor vértice deixa de ser garantidamente ótima.
- A alternativa B está errada, porque Dijkstra não trata ciclos positivos como premissa; a exigência é sobre o sinal dos pesos das arestas, e ciclos negativos são um problema à parte.
- A alternativa C está errada, porque pesos zero não são o problema; o algoritmo funciona normalmente com pesos iguais a zero, e o que falha são pesos negativos.
- A alternativa D está errada, porque afirma o contrário do esperado: Dijkstra não garante caminhos mínimos em grafos com pesos negativos, independentemente de serem direcionados ou não.
- A alternativa E está errada, porque o algoritmo nunca escolhe o vértice de maior distância; ele escolhe sempre o de menor distância provisória, e arestas negativas não estimulam esse tipo de escolha.
💡 Dica: Considere as propriedades do algoritmo de Dijkstra em relação a pesos negativos.
Alternativa por alternativa
Dijkstra fixa distâncias assumindo que extensões só aumentam custo; uma aresta negativa pode reduzir uma distância já fixada, quebrando a correção do método guloso.
O aluno acredita que a restrição do Dijkstra recai sobre ciclos, e não sobre os pesos das arestas. Confunde a condição de validade do algoritmo com a existência de ciclos de peso positivo.
Por que engana: Confundir a aplicação do algoritmo Dijkstra em grafos com arestas negativas, acreditando que ele ainda pode encontrar o caminho mínimo.
O aluno supõe que o algoritmo tolera pesos negativos e que o problema estaria nos pesos zero, invertendo a condição real de validade. Pode ter memorizado vagamente que 'zero' é um caso delicado sem entender a regra de não negatividade.
O aluno lê a frase como se dissesse que Dijkstra garante caminhos mínimos em grafos direcionados, ignorando a palavra 'não' na afirmação e a relação com pesos negativos. Pode também ter se confundido com a ideia de que orientação das arestas resolve o problema.
O aluno imagina que pesos negativos fazem o algoritmo preferir vértices mais distantes, invertendo a lógica do critério de seleção. Não percebe que a regra do Dijkstra é sempre escolher a menor distância provisória.
Raio-X da questão
algoritmo de Dijkstra
diagnostico
algoritmos de grafos · pesos em arestas
Revisar as características do algoritmo de Dijkstra e seu funcionamento com pesos de arestas.
Confundir a aplicação do algoritmo Dijkstra em grafos com arestas negativas, acreditando que ele ainda pode encontrar o caminho mínimo.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Para que o algoritmo de Dijkstra retorne corretamente caminhos mínimos em um grafo (dirigido ou não) com pesos nas…
- No algoritmo de Dijkstra para caminhos mínimos em um grafo com pesos não negativos, qual estrutura de dados é usada para…
- 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…
- No algoritmo de Dijkstra para caminhos mínimos, qual estrutura de dado é comumente usada para selecionar rapidamente o…
- Uma empresa usa um algoritmo que considera dados de tráfego para escolher rotas. Compare: quando o caminho de menor peso…
Todas as questões de Programação - Programação usando grafos e árvores
🔎 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