MO417 - Questão para a prova oral

Número: 145

Enunciado:
Dadas afirmações a seguir sobre o algoritmo de JOHNSON para a resolu??o do problema de Caminhos mais curtos de todos os pares em um grafo, assinale a alternativa INCORRETA:

JOHNSON(G)
1. Calcular G'
2. if BELLMAN-FORD(G',w,s) = FALSE 
3. then imprimir " O grafo de entrada contem um ciclo de peso negativo"
4. else  for cada vertice v de V[G']
5.            do definir h(v) como o valor de delta(s, v) calculado por Bellman-Ford  
6.       for cada aresta (u,v) de E[G']
7.             do wp(u,v) := w(u,v) + h(u) - h(v) // wp = w ponderado

8.    for cada vertice u de V[G]
9.        do executar DIJKSTRA(G, wp, u) para calcular δp(u,v)
                  p/ todo v de V[G] // δp  = δ ponderado 
10.           for cada vertice v de V[G]
11.               do duv := δp(u,v) + h(v)- h(u)
12.   return D

1. É O(V^2 lgV + VE) (Usando Heap de Fibonacci em Dijkstra).
2. É um bom algoritmo para grafos grandes e esparsos.
3. Executa |V| vezes o algoritmo de Dijkstra .
4. Utiliza a representação do grafo por matriz de adjac?ncias.
5. NDA

Autor(a): Renato Hirata