Questão 613141

• Banca: CESPE / CEBRASPE
• Órgão: BRB
• Ano: 2011
• Provas: CESPE - 2011 - BRB - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Conceitos Básicos e Algoritmos

Acerca de algoritmos, estruturas de dados e lógica de programação,
julgue os itens subsequentes.

O algoritmo de Dijkstra utiliza a técnica de relaxamento e produz, ao final de sua execução, uma árvore de caminhos mais curtos entre um vértice origem s e todos os vértices que são alcançáveis a partir de s.

• C. Certo
• E. Errado

Gabarito: C

Comentários

• O algoritmo de Dijkstra resolve o problema de caminhos mais curtos de única origem em um grafo orientado ponderado G = (V, E) para o caso no qual todos os pesos de arestas são não negativos.
  
  O algoritmo de Dijkstra utiliza a técnica de relaxamento de arestas.
  
  Pelo fato do algoritmode Dijkstra sempre escolher o vértice "mais leve" ou "mais próximo" dizemos que ele utiliza uma estratégia gulosa.
  
  Cormen 1ª ed. Pag.470, 471 e 472.

• Algoritmo de Dijkstra

  O algoritmo de Dijkstra é o mais famoso dos algoritmos para cálculo de caminho de custo mínimo entre vértices de um grafo e, na prática, o mais empregado. 
  
  Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. O algoritmo pode ser usado sobre grafos orientados (dígrafos), ou não, e admite que todas as arestas possuem pesos não negativos (nulo é possível). Esta restrição é perfeitamente possível no contexto de redes de transportes, onde as arestas representam normalmente distâncias ou tempos médios de percurso; poderão existir, no entanto, aplicações onde as arestas apresentam pesos negativos, nestes casos o algoritmo não funcionará corretamente.

• Prezados,
  
  O algoritmo de Dijkstra soluciona o problema do caminho mais curto num grafo, dirigido ou não, com arestas de peso não negativo. 
  Ele utiliza a técnica de relaxamento, essa técnica diz que para um arco(u,v), consiste em testar se é possível melhorar o caminho mais curto para v passando por u, em caso afirmativo, atualizar o atributo do nó v.
  
  Portanto a questão está correta.