O algoritmo de Dijkstra é frequentemente utilizado para encontrar o caminho mais curto entre dois nós em um grafo ponderado e não direcionado. Considere as afirmações a seguir sobre o algoritmo de Dijkstra, no contexto de algoritmos de caminhos mínimos em grafos ponderados. Assinale a afirmação correta.

Alternativa D

O algoritmo de Dijkstra é um dos pilares da teoria dos grafos para resolver o problema do caminho mais curto. Para identificar a alternativa correta, precisamos analisar as características fundamentais do algoritmo, suas limitações e sua eficiência computacional.

Análise das Alternativas

A alternativa D é a correta porque descreve com precisão a complexidade de tempo da implementação clássica (ingênua) do algoritmo.

Por que a Alternativa D está correta?

A implementação básica do algoritmo de Dijkstra opera da seguinte forma:

1. Mantém-se uma lista de distâncias iniciais (infinitas, exceto a origem).
2. Em cada passo, seleciona-se o vértice não visitado com a menor distância conhecida. Na versão sem heaps, isso requer uma varredura linear em todos os vértices restantes, custando O(n).
3. Esse processo é repetido n vezes (uma vez para cada vértice).
4. Portanto, a complexidade total torna-se O(n^2), onde n é o número de vértices.

Por que as outras estão incorretas?

• Alternativa A (Pesos Negativos): O algoritmo de Dijkstra baseia-se na premissa de que, uma vez que um caminho mais curto para um nó é encontrado, ele nunca será superado. Arestas com pesos negativos podem violar essa propriedade, fazendo com que o algoritmo falhe. Para esses casos, usamos algoritmos como Bellman-Ford.
• Alternativa B (BFS): O algoritmo de Dijkstra utiliza uma estratégia Gulosa (Greedy), priorizando sempre o nó com a menor distância acumulada. A Busca em Largura (BFS) é usada apenas para grafos não ponderados (ou onde todas as arestas têm peso 1).
• Alternativa C (Ciclos Negativos): O Dijkstra não possui mecanismo nativo para detectar ou reportar ciclos negativos. Se houver um ciclo negativo acessível, o conceito de "caminho mais curto" perde o sentido (pois se pode reduzir a distância infinitamente).
• Alternativa E (Ciclos): Embora o algoritmo funcione em grafos com ciclos positivos, a frase "independentemente da presença de ciclos" é enganosa se considerar ciclos negativos. Além disso, a afirmação da alternativa D é matematicamente mais específica e inquestionável quanto à complexidade de implementação.

Conclusão

A alternativa D é a única que apresenta uma característica técnica correta e verificável sobre a implementação padrão do algoritmo de Dijkstra.