Questão 3064144

• Banca: UFMG
• Órgão: UFMG
• Ano: 2019
• Provas: UFMG - 2019 - UFMG - Técnico de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

O famoso algoritmo de Dijkstra soluciona um problema de grafos direcionados e não direcionados com uma certa complexidade. Qual é esse problema e qual é essa complexidade?

• A. Problema do caminho mínimo com complexidade O (m + n log n) em que m é o número de arestas e n é o número de vértices.
• B. Problema do caminho mínimo com complexidade O (n!) em que n é o número de vértices.
• C. Problema da mochila com complexidade O (m * n) em que m é o número de arestas e n é o número de vértices.
• D. Problema da mochila com complexidade O (m!) em que m é o número de arestas.

Gabarito: A

Comentários

• PRIMEIRAMENTE: O problema da mochila nunca foi resolvido, sendo assim elimina-se C e D.

  SEGUNDAMENTE: O Dijkstra jamais publicou um algoritmo com complexidade tão ruim - O(n!), assim elimina-se a B.

• Força Guerreiro!!!!!!