Sobre o algoritmo de Dijkstra para encontrar caminhos mínimos sobre um grafo \( G=(V,E) \) não-dirigido e com pesos nas arestas. Uma variação comum do algoritmo armazena em cada nó um ponteiro u.p para o seu antecessor no caminho mais curto da raiz até ele. Chame essa variação de DijkstraP.

Defina: o subgrafo S(G) = (V,E’) como um subgrafo de G, cujos vértices são os mesmos de G, mas E’ é um subconjunto de E. Uma aresta (u,v) de E pertence a E’ apenas se, depois de executado DijsktraP, v.p = u;

Marque a alternativa FALSA: