Semana: 19/05/2003 a 23/05/2003
Assunto: Caminhos mais curtos - Fonte Única
Qual das alternativas abaixo está INCORRETA:
A) Para permitir a utilização de grafos com pesos negativos, o algoritmo de Bellman-Ford acaba por visitar algumas arestas mais de uma vez.
B) O algoritmo de Dijkstra é semelhante ao algoritmo de Prim para árvores espalhadas mínimas, porque ambos utilizam um heap para encontrar o vertice "mais leve" a ser adicionado no conjunto dos vértices já selecionados.
C) O algoritmo DAG-SHORTEST-PATH é mais indicado que o algoritmo de Dijkstra para grafos acíclicos e com pesos não negativos, pois seu tempo de execução é Theta(V + E), enquanto que a melhor implementação do algoritmo de Dijkstra leva O(V lg V + E).
D) Para um problema cujo pesos fornecidos são não negativos e o grafo acíclico; e desejamos saber os caminhos MAIS LONGOS do grafo, poderíamos inverter o sinal do vetor de pesos e utilizar o algoritmo de Dijkstra diretamente e obterímos o resultado desejado.
E) n.d.a.
Autor: Nielsen Cassiano Simões
RA: 941614