Algoritmo de Dijkstra

Prévia do material em texto

Algoritmo de Dijkstra 
Qual e o objetivo principal do algoritmo de Dijkstra?
a) Encontrar o caminho mais longo entre dois nos em um grafo
b) Encontrar o caminho de menor custo entre um no origem e todos os demais nos do grafo
c) Ordenar os vertices de um grafo
d) Detectar ciclos em grafos direcionados
Resposta: b) Encontrar o caminho de menor custo entre um no origem e todos os demais nos do
grafo
Explicacao: O algoritmo de Dijkstra e usado para calcular o caminho de menor distancia ou custo
de um vertice inicial para todos os outros vertices em um grafo com pesos nao negativos.
Qual e a condicao fundamental para que o algoritmo de Dijkstra funcione corretamente?
a) O grafo deve ser direcionado
b) Os pesos das arestas devem ser numeros inteiros
c) Os pesos das arestas devem ser nao negativos
d) O grafo deve ser conexo
Resposta: c) Os pesos das arestas devem ser nao negativos
Explicacao: Dijkstra nao funciona corretamente com arestas de peso negativo, pois pode
subestimar distancias em certos caminhos.
No algoritmo de Dijkstra, como e escolhido o proximo vertice a ser processado?
a) O vertice com o maior peso acumulado
b) O vertice com a menor distancia temporaria ainda nao processada
c) O vertice com maior numero de conexoes
d) O vertice que aparece primeiro na lista de adjacencia
Resposta: b) O vertice com a menor distancia temporaria ainda nao processada
Explicacao: O algoritmo sempre seleciona o vertice com a menor distancia estimada para garantir
que os caminhos mais curtos sejam descobertos primeiro.
O que ocorre com a distancia de um vertice quando o algoritmo de Dijkstra o processa?
a) Ela e aumentada para refletir o caminho mais longo
b) Ela e marcada como definitiva, representando a menor distancia conhecida ate entao
c) Ela e reiniciada para infinito
d) Ela e ignorada para agilizar o algoritmo
Resposta: b) Ela e marcada como definitiva, representando a menor distancia conhecida ate entao
Explicacao: Quando um vertice e processado, sua distancia minima ate o vertice origem e
finalizada, pois nao havera caminho mais curto a partir daquele ponto.
Quais estruturas de dados sao geralmente utilizadas para implementar o algoritmo de Dijkstra de
forma eficiente?
a) Listas encadeadas simples
b) Pilhas
c) Filas de prioridade (heaps)
d) Arrays estaticos
Resposta: c) Filas de prioridade (heaps)
Explicacao: O uso de uma fila de prioridade, como um heap binario, permite a selecao eficiente do
vertice com a menor distancia durante a execucao do algoritmo.
Como o algoritmo de Dijkstra inicializa as distancias dos vertices?
a) Com zero para todos os vertices
b) Com infinito para todos os vertices, exceto o vertice origem que e zero
c) Com a soma dos pesos de todas as arestas do grafo
d) Com valores aleatorios para agilizar a execucao
Resposta: b) Com infinito para todos os vertices, exceto o vertice origem que e zero
Explicacao: Isso indica que a distancia para todos os nos e desconhecida inicialmente, exceto para
o no de origem, cujo custo e zero.
Quando o algoritmo de Dijkstra termina?
a) Quando todos os vertices foram processados e suas distancias finais definidas
b) Quando encontra o menor caminho para o vertice destino especifico
c) Quando a soma dos pesos for maior que um limite pre-definido
d) Quando o grafo estiver vazio
Resposta: a) Quando todos os vertices foram processados e suas distancias finais definidas
Explicacao: O algoritmo percorre todos os nos alcancaveis para garantir o menor caminho ate cada
um deles.
O que acontece se o algoritmo de Dijkstra for aplicado em um grafo que contem arestas com peso
negativo?
a) Ele funcionara normalmente
b) Ele podera retornar caminhos incorretos ou infinitos
c) Ele ira ignorar as arestas de peso negativo
d) Ele detectara automaticamente e corrigira o peso
Resposta: b) Ele podera retornar caminhos incorretos ou infinitos
Explicacao: A presenca de pesos negativos pode causar loops de atualizacao infinitos, fazendo
com que o algoritmo nao produza resultados validos.
Qual e a complexidade de tempo tipica do algoritmo de Dijkstra implementado com uma fila de
prioridade usando um heap binario?
a)
O(V
2
)
b)
O(E+VlogV)
c)
O(V+E
2
)
d)
O(logV)
Resposta: b)
O(E+VlogV)
Explicacao: O tempo depende do numero de vertices
V e arestas
E, e a implementacao com heap otimiza as operacoes de extracao do menor elemento.
Qual e a funcao do vetor (ou lista) de predecessores durante a execucao do algoritmo de Dijkstra?
a) Contar quantas vezes um vertice foi visitado
b) Armazenar o caminho minimo encontrado ate cada vertice
c) Guardar as distancias temporarias para cada vertice
d) Identificar ciclos no grafo
Resposta: b) Armazenar o caminho minimo encontrado ate cada vertice
Explicacao: O vetor de predecessores registra o no anterior no caminho de menor custo para
reconstruir a rota ao final.
Em um grafo com 5 vertices, o algoritmo de Dijkstra encontra as distancias minimas a partir do
vertice 1. Se um vertice nao e alcancavel a partir do vertice 1, qual sera seu valor final de distancia?
a) 0
b) 1
c) Infinito (ou um valor muito grande)
d) -1
Resposta: c) Infinito (ou um valor muito grande)
Explicacao: Como nao ha caminho para esse vertice, a distancia permanece infinita, indicando
inacessibilidade.
Por que o algoritmo de Dijkstra e considerado um algoritmo guloso?
a) Porque tenta resolver subproblemas maiores primeiro
b) Porque escolhe localmente o proximo vertice com a menor distancia, esperando uma solucao
global otima
c) Porque visita todos os vertices sem criterio
d) Porque usa uma abordagem recursiva para encontrar a solucao
Resposta: b) Porque escolhe localmente o proximo vertice com a menor distancia, esperando uma
solucao global otima
Explicacao: O algoritmo toma decisoes locais otimas em cada passo, garantindo a solucao otima
final.
Suponha que voce queira encontrar o menor caminho entre dois vertices especificos em um grafo
usando o algoritmo de Dijkstra. Como pode otimizar o processo?
a) Executar o algoritmo completo para todos os vertices e depois selecionar o caminho desejado
b) Interromper a execucao do algoritmo assim que o vertice destino for processado
c) Ignorar as arestas com peso maior que um valor definido
d) Utilizar busca em largura no lugar do Dijkstra
Resposta: b) Interromper a execucao do algoritmo assim que o vertice destino for processado
Explicacao: Apos determinar o menor caminho para o destino, nao ha necessidade de continuar
processando outros vertices.
O que significa a expressao relaxar uma aresta no contexto do algoritmo de Dijkstra?
a) Atualizar o peso da aresta para um valor menor
b) Ajustar a distancia estimada de um vertice vizinho, se um caminho mais curto for encontrado
c) Remover a aresta do grafo para simplificacao
d) Marcar a aresta como percorrida
Resposta: b) Ajustar a distancia estimada de um vertice vizinho, se um caminho mais curto for
encontrado
Explicacao: Relaxar uma aresta significa verificar se passar por um vertice pode diminuir a distancia
para um vertice adjacente e atualizar a distancia se for o caso.
E possivel utilizar o algoritmo de Dijkstra para encontrar caminhos minimos em grafos nao
conexos?
a) Sim, para os vertices acessiveis a partir do vertice origem
b) Nao, pois exige que o grafo seja totalmente conexo
c) Sim, mas apenas se o grafo for dirigido
d) Nao, a nao ser que o grafo nao tenha pesos
Resposta: a) Sim, para os vertices acessiveis a partir do vertice origem
Explicacao: O algoritmo computa caminhos minimos para os nos que podem ser alcancados; os
demais terao distancia infinita.
Qual e o impacto de um grafo ser dirigido para a execucao do algoritmo de Dijkstra?
a) O algoritmo nao funciona em grafos dirigidos
b) O algoritmo considera a direcao das arestas para calcular os caminhos minimos
c) O algoritmo ignora a direcao das arestas
d) O algoritmo sempre retorna a distancia maxima possivel
Resposta: b) O algoritmo considera a direcao das arestas paracalcular os caminhos minimos
Explicacao: Em grafos dirigidos, so se pode seguir o sentido das arestas para alcancar outros
vertices.
Como o algoritmo de Dijkstra trata os nos que ja foram processados?
a) Eles sao revisitados a cada relaxamento
b) Sao marcados como fechados e nao sao processados novamente
c) Sao ignorados desde o inicio
d) Sao usados para calcular ciclos
Resposta: b) Sao marcados como fechados e nao sao processados novamente
Explicacao: Uma vez que o menor caminho para um vertice e conhecido, ele nao e mais alterado
nem reprocessado.
Qual e a diferenca principal entre o algoritmo de Dijkstra e o algoritmo de Bellman-Ford?
a) Dijkstra funciona apenas com pesos negativos
b) Bellman-Ford pode lidar com pesos negativos, enquanto Dijkstra nao
c) Bellman-Ford e mais rapido que Dijkstra em todos os casos
d) Dijkstra encontra ciclos negativos, Bellman-Ford nao
Resposta: b) Bellman-Ford pode lidar com pesos negativos, enquanto Dijkstra nao
Explicacao: Bellman-Ford e mais geral, podendo lidar com arestas negativas, mas e mais lento que
Dijkstra.
Qual dessas alternativas representa uma aplicacao pratica do algoritmo de Dijkstra?
a) Compressao de arquivos
b) Roteamento de pacotes em redes de computadores
c) Calculo de areas em geometria
d) Criptografia
Resposta: b) Roteamento de pacotes em redes de computadores
Explicacao: O algoritmo e usado para determinar o caminho mais curto para enviar dados de um
ponto a outro em redes.
Durante a execucao do algoritmo, se a distancia atual para um vertice
v e 7 e encontramos um caminho alternativo com custo 5, o que acontece?
a) A distancia para
v permanece 7
b) A distancia para
v e atualizada para 5
c) O algoritmo termina imediatamente
d) O vertice
v e removido do grafo
Resposta: b) A distancia para
v e atualizada para 5
Explicacao: Sempre que um caminho mais curto e encontrado, a distancia para o vertice e
atualizada.
Se um grafo possui
V vertices e
E arestas, qual e a principal limitacao pratica do algoritmo de Dijkstra para grafos muito grandes?
a) O algoritmo nao suporta mais de 100 vertices
b) A complexidade computacional pode se tornar alta, especialmente se nao usar estruturas
eficientes
c) O algoritmo retorna sempre caminhos incorretos para grafos grandes
d) Ele nao funciona com grafos completos
Resposta: b) A complexidade computacional pode se tornar alta, especialmente se nao usar
estruturas eficientes
Explicacao: Para grafos grandes, otimizacoes como uso de heaps sao importantes para manter o
algoritmo eficiente.
Quando se usa uma matriz de adjacencia para representar o grafo no algoritmo de Dijkstra, qual e a
complexidade tipica?
a)
O(V
2
)
b)
O(ElogV)
c)
O(VlogV+E)
d)
O(E
2
)
Resposta: a)
O(V
2
)
Explicacao: A matriz de adjacencia exige verificar todas as possiveis conexoes, resultando em
complexidade quadratica para o numero de vertices.
Como o algoritmo de Dijkstra trata a distancia inicial do vertice origem para ele mesmo?
a) Inicializa com infinito
b) Inicializa com zero
c) Inicializa com o peso da primeira aresta
d) Inicializa com um valor aleatorio
Resposta: b) Inicializa com zero
Explicacao: A distancia do vertice origem para ele mesmo e zero, pois nao ha custo para chegar
nele mesmo.
E possivel aplicar o algoritmo de Dijkstra em grafos ciclicos?
a) Nao, pois ciclos invalidam o algoritmo
b) Sim, desde que nao haja arestas de peso negativo
c) Apenas em grafos aciclicos direcionados
d) Apenas se o ciclo for simples
Resposta: b) Sim, desde que nao haja arestas de peso negativo
Explicacao: Ciclos nao impedem a execucao do algoritmo, contanto que nao causem somas
negativas.
Qual das opcoes abaixo descreve melhor o funcionamento do algoritmo de Dijkstra em relacao ao
caminho mais curto?
a) Ele calcula o caminho mais curto somente para um destino especifico
b) Ele calcula o caminho mais curto da origem para todos os outros vertices do grafo
c) Ele calcula o caminho mais longo para cada vertice
d) Ele calcula somente se o grafo for aciclico
Resposta: b) Ele calcula o caminho mais curto da origem para todos os outros vertices do grafo
Explicacao: A saida do algoritmo inclui as menores distancias para todos os vertices acessiveis a
partir da origem.
O que deve ser armazenado para reconstruir o caminho mais curto apos o termino do algoritmo?
a) As distancias finais para cada vertice
b) Os predecessores de cada vertice no caminho mais curto
c) Os pesos de todas as arestas do grafo
d) A lista de todos os vertices processados
Resposta: b) Os predecessores de cada vertice no caminho mais curto
Explicacao: Com os predecessores, pode-se remontar o caminho de origem ate o destino desejado.
O algoritmo de Dijkstra pode ser modificado para trabalhar em grafos onde as arestas representam
custos variaveis ao longo do tempo?
a) Sim, mas ele precisa ser adaptado para reprocessar os caminhos conforme os custos mudam
b) Nao, ele so funciona com custos fixos
c) Sim, sem nenhuma modificacao
d) Nao, porque o algoritmo nao considera pesos nas arestas
Resposta: a) Sim, mas ele precisa ser adaptado para reprocessar os caminhos conforme