MO417 - Questão para a prova oral
Número: 2003-152Enunciado: Assinale a alternativa INCORRETA para um grafo ponderado G com V vértices e E arestas:
A) As instâncias de entrada para problemas de caminho mais curto de origem única não podem ter arestas de peso negativo.
B) Para resolver o problema de caminho mais curto de destino único deves-se inverter o sentido de cada aresta e resolver o problema de caminho mais curto de origem única.
C) O algoritmo de Bellman-Ford é executado em tempo O(EV), enquanto o de Dijkstra pode ser executado em O(V+ElgV) usando a implementação de heap binário.
D) O algoritmo de Dijkstra mantém uma fila de prioridade mínima e utiliza três operações desta estrutura de dados: INSERT, EXTRACT-MIN, DECREASE-KEY.
E) NDA
Ideia original de: Ricardo Luís Lachi
Nenhum comentário:
Postar um comentário