Qual é a complexidade de tempo do algoritmo de Dijkstra? A) O(n) B) O(n log n) C) O(n^2) D) O(2^n) E) O(n!)

A complexidade de tempo do algoritmo de Dijkstra depende da implementação utilizada. A forma mais comum de implementar o algoritmo é usando uma fila de prioridade (heap), o que resulta em uma complexidade de O(n log n). No entanto, se o algoritmo for implementado usando uma matriz de adjacência sem otimizações, a complexidade pode ser O(n^2). Analisando as alternativas: A) O(n) - Não é correta para o algoritmo de Dijkstra. B) O(n log n) - Correta se usar uma fila de prioridade. C) O(n^2) - Correta em uma implementação simples com matriz de adjacência. D) O(2^n) - Não é correta. E) O(n!) - Não é correta. Portanto, a resposta correta, considerando a implementação mais eficiente, é: B) O(n log n).