Prova AV
Algoritmos e Complexidade
O algoritmo de Dijkstra é frequentemente utilizado para encontrar o caminho mais curto entre dois nós em um grafo ponderado e não direcionado. Considera 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.
A O algoritmo de Dijkstra pode ser aplicado eficientemente em grafos que contenham arestas com pesos negativos para encontrar o caminho mais curto.
B O algoritmo de Dijkstra utiliza uma abordagem de busca em largura (BFS - Breadth-First Search) como sua estratégia principal para encontrar o caminho mais curto.
C O algoritmo de Dijkstra pode identificar e reportar a presença de ciclos negativos em um grafo.
D O algoritmo de Dijkstra, quando implementado sem otimizações como heap de Fibonacci, possui uma complexidade de tempo de O(n2) para n vértices.
