Sejam as seguintes afirmativas relativas a algoritmos em grafos:

I. O algoritmo de caminho mais curto (mínimo) proposto por Dijkstra encontra os caminhos mais curtos a partir de uma origem em um grafo direcionado ponderado, em que os pesos podem ser positivos ou negativos.

II. Os algoritmos de Prim e Kruskal para obtenção da árvore geradora mínima de um grafo são algoritmos gulosos com ordem de complexidade polinomial.

III. O algoritmo de Busca em Profundidade em grafos é base para a detecção de componentes fortemente conectados.

Com relação aos algoritinos em gupos, assinale a opção CORRETA.