Algoritmo de Floyd-Warshall

Prévia do material em texto

Algoritmo de Floyd-Warshall 
O Algoritmo de Floyd-Warshall e utilizado para resolver qual tipo de problema?
a) Encontrar a arvore geradora minima de um grafo
b) Calcular o caminho minimo entre todos os pares de vertices
c) Determinar a ordem topologica de um grafo
d) Detectar componentes fortemente conexas
Resposta explicativa: O Floyd-Warshall e um algoritmo de todos os caminhos minimos (all-pairs
shortest paths), ou seja, encontra a menor distancia entre todos os pares de vertices de um grafo
ponderado.
Qual a complexidade de tempo do Algoritmo de Floyd-Warshall?
a) O(V log V)
b) O(V2)
c) O(V3)
d) O(V + E)
Resposta explicativa: O algoritmo percorre tres lacos aninhados sobre os vertices, resultando em
uma complexidade de O(V3), sendo mais eficiente para grafos pequenos ou densos.
O algoritmo de Floyd-Warshall pode lidar com arestas de peso negativo?
a) Sim, mas apenas se nao houver ciclos negativos
b) Nao, ele falha em qualquer peso negativo
c) Sim, incluindo ciclos negativos
d) Apenas se o grafo for direcionado
Resposta explicativa: O algoritmo aceita pesos negativos, mas nao pode lidar com ciclos negativos,
pois isso levaria a uma diminuicao infinita das distancias.
Qual estrutura e usada para armazenar as distancias entre os vertices no Floyd-Warshall?
a) Lista encadeada
b) Matriz de adjacencia
c) Arvore binaria
d) Tabela hash
Resposta explicativa: O Floyd-Warshall utiliza uma matriz de adjacencia modificada chamada
matriz de distancias, que e atualizada a cada iteracao para armazenar as menores distancias entre
pares de vertices.
Se um grafo tem 4 vertices, quantas iteracoes principais o algoritmo realizara?
a) 4
b) 8
c) 12
d) 16
Resposta explicativa: O laco mais externo do algoritmo percorre todos os vertices, entao havera 4
iteracoes principais, uma para cada vertice intermediario possivel.
O que representa a variavel k no pseudocodigo do Algoritmo de Floyd-Warshall?
a) O vertice inicial
b) O vertice final
c) O vertice intermediario usado para atualizacao das distancias
d) O numero de arestas processadas
Resposta explicativa: A variavel k representa o vertice intermediario que esta sendo considerado
para verificar se existe um caminho mais curto passando por ele.
Como o algoritmo trata a distancia de um vertice para ele mesmo no inicio?
a) Atribui zero
b) Atribui infinito
c) Atribui um valor aleatorio
d) Atribui o peso da aresta de entrada
Resposta explicativa: A distancia de um vertice para ele mesmo e zero, pois nao ha custo em
permanecer no mesmo ponto.
Qual e a condicao usada para atualizar uma distancia no algoritmo?
a) Se dist[i][k] * dist[k][j]