MO417 - Questão para a prova oral

Número: 151

Enunciado:
Podemos resolver um problema de caminhos mais curtos de todos os pares executando um algoritmo de caminhos mais curtos de origem única |V| vezes, uma para cada vértice usado como a origem. Se todos os pesos de arestas são não negativos, podemos usar o algoritmo de Dijkstra. Escolha a alternativa que corresponde ao tempo de execução, respectivamente, se usarmos as implementações: arranjo linear da fila de prioridades; heap binário na fila de prioridade mínima; fila de prioridade mínima com um heap de Fibonacci.

1. O(V²); O(V E lg V); O(V² lg V + V E)
2. O(V²); O(V² lg V + V E); O(V E lg V);
3. O(V³); O(V E lg V); O(V² lg V + V E)
4. O(V³); O(V² lg V + V E); O(V E lg V);
5. NDA

Autor(a): José Vieira Maciel Borges