dav

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Sobre o tempo de execução de cálculo de caminho mínimo entre dois vértices em um grafo de V vértices e E arestas é INCORRETO afirmar:

1. O tempo de execução pode ser  o(V*E) somente se não houver ciclos ou se não houver arestas com pesos negativos
2. Se não houver ciclos no grafo, o tempo de execução pode pertencer a O(V+E)
3. O tempo de execução é O(V*E) para qualquer grafo que contenha ciclos e arestas de pesos negativos
4. Para qualquer grafo que contém ciclos e não contém arestas de peso negativo o tempo de execução pode  pertencer a O(V^2)
5. NDA

Ideia original de: Daniel Vidal