Logo Passei Direto
Buscar

Outros

Outros
Considere o seguinte grafo e a matriz de adjacência modificada. Deseja-se o caminho mínimo entre os nós A e F, empregando-se o algoritmo de Dijkstra.

A graph with nodes labeled A, B, C, D, E, and F. The edges have weights, and the graph is used to illustrate the Dijkstra algorithm for finding the shortest path between nodes A and F.

Em uma etapa inicial, o algoritmo inicializa o conjunto de nós IN com:
a, O nó A.
b, O nó B.
c, O nó F.
d, O nó C.
e, Conjunto vazio.
User badge image
CuriosidadesGerais

ano passado

User badge image
CuriosidadesGerais

ano passado

QUESTIONÁRIO UNIDADE II
5 pág.

QUESTIONÁRIO UNIDADE II

UNIP

Respostas

User badge image

Ed Verified user icon

ano passado

Para determinar qual é o conjunto inicial de nós IN no algoritmo de Dijkstra, precisamos entender que, no início do algoritmo, apenas o nó de partida (neste caso, o nó A) é adicionado ao conjunto de nós IN. Os outros nós ainda não foram visitados e, portanto, não fazem parte desse conjunto. Vamos analisar as alternativas: a) O nó A. - Correto, pois o algoritmo começa com o nó de origem. b) O nó B. - Incorreto, pois o nó B não é o nó de partida. c) O nó F. - Incorreto, pois o nó F é o destino, não o ponto de partida. d) O nó C. - Incorreto, pois o nó C não é o nó de partida. e) Conjunto vazio. - Incorreto, pois o conjunto inicial deve conter o nó A. Portanto, a alternativa correta é: a) O nó A.

Essa resposta te ajudou?

0
Dislike0

Ainda não achou a resposta?

  • Integrado com os principais modelos de IA do mercado
  • Respostas em segundos
  • IA treinada para estudantes brasileiros.
PasseIA logoEvolua sua forma de estudar

Cadastre-se ou realize login

Ainda com dúvidas?

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

Essa pergunta também está no material:

QUESTIONÁRIO UNIDADE II
5 pág.

QUESTIONÁRIO UNIDADE II

UNIP

Mais perguntas desse material

Considere as seguintes asserções sobre o algoritmo de Kruskal: I - Todas as arestas são ordenadas por peso. II - Verifica-se cada aresta da sequência ordenada para ver se pode ser considerada parte da árvore em construção. III - Uma aresta é adicionada à árvore se não aparece nenhum ciclo depois de sua inclusão. São asserções verdadeiras:
a. I, II e III.
b. Apenas I e II.
c. Apenas I e III.
d. Apenas II e III.
e. Apenas III.

O algoritmo que calcula o caminho mínimo de um nó particular a qualquer outro nó: a. Kruskal. b. Dijkstra. c. Warshall. d. Floyd. e. Bellman-Ford.

Considere as seguintes asserções: I - As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, distâncias entre cidades. II - As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, tempos que separam a execução de certas tarefas. III - As arestas de um grafo podem estar associadas a certos pesos que representam, por exemplo, custos de se transmitir informação entre localidades. São corretas as afirmações:
a. Apenas I.
b. Apenas II.
c. Apenas III.
d. I, II e III.
e. Apenas I e II.

A respeito do algoritmo concebido por Stephen Warshal e implementado por Robert Floyd, é incorreto afirmar: a. Encontra todos os menores caminhos a partir de um vértice qualquer para qualquer outro. b. O grafo pode incluir pesos negativos. c. Trata-se de um algoritmo O(n3). d. Seu desempenho em consumo de memória é combinatório. e. Faz uso de matriz de adjacência modificada.

Na segunda iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, o nó selecionado para o conjunto IN é B, porque:
a. É adjacente a A.
b. É lexicograficamente sucessor de A.
c. É selecionado empiricamente.
d. É o de menor distância.
e. O nó B não é o selecionado.

Na terceira iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F: I - O nó C é selecionado. PORQUE II - Comparam-se as distâncias entre o nó A e os demais C, D, E e F, passando-se por B, ou não. Os valores do vetor d e o vetor s podem ser reescritos segundo o menor valor resultante da comparação. Ao final obtém-se o nó C como aquele que apresenta o menor valor no vetor d. Pode-se afirmar que:
a. I e II são verdadeiras e II justifica I.
b. I e II são verdadeiras, mas II não justifica I.
c. Apenas I é verdadeira.
d. Apenas II é verdadeira.
e. I e II são afirmações falsas.

Na quinta iteração do algoritmo de Dijkstra para o caminho mínimo entre os nós A e F, o nó selecionado para o conjunto IN é:
a, A, B, C, D, F.
b, A, B, C, E, F.
c, B, A, C, F.
d, A, B, E, F.
e, F, E, B, C, A.

Mais conteúdos dessa disciplina