Algoritmos e Estrutura de Dados · UFMG · 2019 | Questão sqc-qq559631

GabaritoA — 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.

Algoritmo de Dijkstra: problema e complexidade

Gabarito: letra A. O algoritmo de Dijkstra resolve o problema do caminho mínimo (ou caminho mais curto) em grafos direcionados ou não direcionados, com arestas de peso não negativo. A complexidade típica com o uso de uma fila de prioridades (heap binário) é $O((n+m)\log n)$ , que equivale a $O(m + n \log n)$ quando $m \geq n$ . Essa é exatamente a descrição da alternativa A.

A banca cobra o conhecimento clássico sobre um dos algoritmos mais importantes da teoria dos grafos. Dijkstra não resolve o problema da mochila (knapsack), e sua complexidade não é fatorial nem exponencial.

Algoritmo de Dijkstra: Problema resolvido (Caminho mínimo, Grafos direcionados ou não, Arestas com peso não negativo); Complexidade (heap binário) (O((m + n) log n), O(m + n log n) (se m ≥ n)); Não resolve (Problema da mochila, Caixeiro viajante)

Alternativa A — ✅ Correta ⟵ GABARITO

O algoritmo de Dijkstra encontra o caminho de menor custo entre um vértice fonte e todos os demais vértices do grafo. A complexidade $O(m + n \log n)$ é obtida com implementação eficiente usando heap de Fibonacci ( $O(m + n \log n)$ ) ou heap binário ( $O((m+n)\log n)$ ). Ambas estão dentro da notação apresentada. O enunciado considera o caso em que $m \geq n$ , simplificando para $O(m + n \log n)$ .

Alternativa B — ❌ Incorreta

Afirma complexidade $O(n!)$ , que é fatorial. Algoritmos com essa complexidade são inviáveis para instâncias grandes e não correspondem ao algoritmo de Dijkstra. O problema do caminho mínimo é polinomial (P), e Dijkstra tem complexidade quase linear no número de arestas.

Alternativa C — ❌ Incorreta

Associa o algoritmo de Dijkstra ao problema da mochila (knapsack), que é um problema de otimização combinatória NP-difícil. Dijkstra resolve caminho mínimo, não mochila. A complexidade $O(m \cdot n)$ também não se aplica a Dijkstra; o algoritmo de Dijkstra não tem esse custo.

Alternativa D — ❌ Incorreta

Novamente atribui a Dijkstra o problema da mochila, com complexidade $O(m!)$ — fatorial no número de arestas. Além de ser o problema errado, a complexidade é absurda para Dijkstra.

NÃO CAIA NESSA!

Para não confundir, lembre-se: Dijkstra = caminho mínimo em grafos com pesos não negativos. A complexidade é $O((V+E)\log V)$ ou $O(E + V \log V)$ nas formas mais comuns. Jamais associe Dijkstra a problemas como mochila, caixeiro viajante ou hamiltoniano.

Gabarito: letra A.