ant

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido G=(V,E):
 

  

Seja w e W a função de peso e a matriz de pesos do grafo G respetivamente. Suponha que seu vetor de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa correta sobre os caminhos mais curtos entre todos os pares de vértices do grafo G: 

1.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16. 

2.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.

3.)Johnson(G,w) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16.
4.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga