Logo Passei Direto
Buscar

Estrutura de Dados

Outros
Em Floyd-Warshall, como e representada a ausencia de aresta entre dois vertices no inicio do algoritmo?
a) Com 0
b) Com infinito
c) Com -1
d) Com o peso medio das arestas
User badge image
Questões para Estudantes

há 2 meses

User badge image
Questões para Estudantes

há 2 meses

Algoritmo de Floyd-Warshall
9 pág.

Algoritmo de Floyd-Warshall

Respostas

User badge image

Ed Verified user icon

há 2 meses

No algoritmo de Floyd-Warshall, a ausência de aresta entre dois vértices é representada por um valor que indica que não há conexão direta entre eles. Analisando as alternativas: a) Com 0 - Isso não é correto, pois 0 geralmente representa a distância de um vértice para ele mesmo. b) Com infinito - Esta é a representação correta, pois indica que não há caminho entre os vértices. c) Com -1 - Não é uma representação padrão no algoritmo. d) Com o peso médio das arestas - Isso também não é correto, pois não se utiliza o peso médio para representar a ausência de arestas. Portanto, a alternativa correta é: b) Com infinito.

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Algoritmo de Floyd-Warshall
9 pág.

Algoritmo de Floyd-Warshall

Mais perguntas desse material

Qual e o principal objetivo do algoritmo de Floyd-Warshall?
a) Encontrar o caminho mais longo entre dois vertices
b) Encontrar o caminho mais curto entre todos os pares de vertices em um grafo ponderado
c) Determinar se um grafo e conexo
d) Ordenar os vertices de um grafo

O algoritmo de Floyd-Warshall funciona corretamente em grafos com arestas de peso negativo?
a) Sim, desde que nao haja ciclos negativos
b) Nao, ele falha sempre com pesos negativos
c) Sim, mesmo com ciclos negativos
d) Somente em grafos direcionados

Qual e a complexidade de tempo do algoritmo de Floyd-Warshall para um grafo com V vertices?
a) O(V^2)
b) O(V^3)
c) O(VlogV)
d) O(E+VlogV)

O algoritmo de Floyd-Warshall pode ser usado em grafos nao ponderados?
a) Sim, funciona corretamente
b) Nao, apenas grafos ponderados
c) Apenas se forem direcionados
d) Apenas em grafos aciclicos

Em Floyd-Warshall, o que significa a expressao dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])?
a) Atualizar a distancia de i a j considerando um possivel caminho passando por k
b) Somar todos os caminhos entre i e j
c) Encontrar o caminho mais longo entre i e j
d) Remover ciclos do grafo

Qual e a diferenca principal entre os algoritmos de Floyd-Warshall e Dijkstra?
a) Floyd-Warshall encontra caminhos mais curtos de todos os pares, Dijkstra de uma unica fonte
b) Floyd-Warshall funciona apenas em grafos aciclicos, Dijkstra em qualquer grafo
c) Dijkstra lida com pesos negativos, Floyd-Warshall nao
d) Nao ha diferenca significativa

Floyd-Warshall pode ser usado para detectar ciclos negativos em um grafo?
a) Sim
b) Nao
c) Apenas em grafos direcionados
d) Apenas em grafos nao ponderados

Qual e a interpretacao do valor final de dist[i][j] no algoritmo de Floyd-Warshall?
a) O caminho mais longo entre i e j
b) O caminho mais curto entre i e j
c) A quantidade de arestas entre i e j
d) O numero de ciclos no grafo

Qual estrutura de dados e normalmente utilizada para armazenar as distancias no algoritmo de Floyd-Warshall?
a) Lista ligada
b) Matriz V×V
c) Fila de prioridade
d) Pilha

Qual e a condicao inicial para dist[i][j] antes de iniciar o algoritmo?
a) 0 para i = j e infinito para i = j, exceto se houver aresta direta
b) 1 para todos os pares
c) Infinito para todos os pares
d) 0 para todos os pares

Mais conteúdos dessa disciplina