Algoritmo de Dijkstra

Prévia do material em texto

Algoritmo de Dijkstra 
Qual e o objetivo principal do algoritmo de Dijkstra?
a) Encontrar o menor caminho entre todos os pares de vertices de um grafo.
b) Encontrar o caminho mais longo entre dois vertices.
c) Encontrar o menor caminho entre dois vertices de um grafo ponderado.
d) Encontrar o maior ciclo em um grafo.
Resposta correta: c) Encontrar o menor caminho entre dois vertices de um grafo ponderado.
Explicacao: O algoritmo de Dijkstra tem como objetivo encontrar o menor caminho de um vertice de
origem para todos os outros vertices de um grafo ponderado com arestas de pesos nao negativos.
O algoritmo de Dijkstra pode ser utilizado em grafos com arestas de peso negativo?
a) Sim, sempre funciona corretamente.
b) Nao, ele nao funciona corretamente em grafos com arestas de peso negativo.
c) Sim, mas com algumas modificacoes.
d) Nao, mas funciona em grafos com pesos negativos em alguns casos.
Resposta correta: b) Nao, ele nao funciona corretamente em grafos com arestas de peso negativo.
Explicacao: O algoritmo de Dijkstra nao funciona corretamente quando o grafo possui arestas de
peso negativo, pois ele assume que uma vez que um vertice e visitado com a menor distancia, nao
ha necessidade de revisa-lo.
Qual a estrutura de dados comumente usada para implementar o algoritmo de Dijkstra?
a) Pilha
b) Fila de prioridade (min-heap)
c) Lista ligada
d) Arvore binaria
Resposta correta: b) Fila de prioridade (min-heap)
Explicacao: O algoritmo de Dijkstra utiliza uma fila de prioridade (geralmente implementada com um
min-heap) para escolher o proximo vertice com a menor distancia de maneira eficiente.
No algoritmo de Dijkstra, qual e a principal operacao realizada ao selecionar um vertice para visitar?
a) Adicionar o vertice ao final da lista de resultados.
b) Atualizar a distancia do vertice para o vertice de origem.
c) Atribuir o valor de distancia infinito aos vertices adjacentes.
d) Remover o vertice com a maior distancia do conjunto de vertices nao visitados.
Resposta correta: b) Atualizar a distancia do vertice para o vertice de origem.
Explicacao: A principal operacao do algoritmo de Dijkstra e atualizar a distancia minima de um
vertice a partir do vertice de origem, revisando suas distancias atraves de seus vizinhos.
Quando o algoritmo de Dijkstra termina sua execucao?
a) Quando todos os vertices sao visitados.
b) Quando o vertice de destino e alcancado.
c) Quando a distancia de todos os vertices e infinita.
d) Quando a fila de prioridade esta vazia.
Resposta correta: d) Quando a fila de prioridade esta vazia.
Explicacao: O algoritmo de Dijkstra termina quando nao ha mais vertices na fila de prioridade, o que
significa que todos os vertices acessiveis foram visitados e suas distancias minimas foram
determinadas.
Qual e a complexidade de tempo do algoritmo de Dijkstra usando uma fila de prioridade
implementada com um min-heap?
a) O(n)
b) O(n2)
c) O((V + E) log V), sendo V o numero de vertices e E o numero de arestas
d) O(V log E)
Resposta correta: c) O((V + E) log V), sendo V o numero de vertices e E o numero de arestas
Explicacao: A complexidade do algoritmo de Dijkstra com uma fila de prioridade implementada
como um min-heap e O((V + E) log V), onde V e o numero de vertices e E o numero de arestas no
grafo.
Qual e o papel da tabela de distancias no algoritmo de Dijkstra?
a) Armazenar os vertices ja visitados.
b) Guardar a distancia minima conhecida de cada vertice em relacao a origem.
c) Registrar as arestas mais curtas do grafo.
d) Determinar o caminho final entre os vertices.
Resposta correta: b) Guardar a distancia minima conhecida de cada vertice em relacao a origem.
Explicacao: A tabela de distancias mantem a distancia minima conhecida de cada vertice em
relacao ao vertice de origem, que e atualizada a medida que o algoritmo avanca.
Em que tipo de grafo o algoritmo de Dijkstra nao pode ser utilizado?
a) Em grafos dirigidos.
b) Em grafos com ciclos.
c) Em grafos com arestas de peso negativo.
d) Em grafos ponderados.
Resposta correta: c) Em grafos com arestas de peso negativo.
Explicacao: O algoritmo de Dijkstra nao pode ser utilizado em grafos com arestas de peso negativo,
pois ele assume que a distancia mais curta de um vertice nunca sera alterada apos ser calculada, o
que nao e verdade quando ha arestas de peso negativo.
No algoritmo de Dijkstra, qual operacao e realizada a cada iteracao para relaxar uma aresta?
a) Atualizar a distancia de um vertice adjacente se a distancia atraves do vertice atual for menor
que a distancia ja registrada.
b) Marcar o vertice adjacente como visitado.
c) Adicionar o vertice adjacente a fila de prioridade.
d) Remover o vertice atual da fila de prioridade.
Resposta correta: a) Atualizar a distancia de um vertice adjacente se a distancia atraves do vertice
atual for menor que a distancia ja registrada.
Explicacao: O processo de relaxamento no algoritmo de Dijkstra envolve atualizar a distancia de um
vertice adjacente se a distancia atraves de um vertice atual for menor do que a distancia ja
registrada.
Qual e o formato da tabela de distancias utilizada no algoritmo de Dijkstra para armazenar os
resultados?
a) Uma matriz de adjacencia.
b) Um vetor de distancias minimas.
c) Uma lista de arestas ponderadas.
d) Uma lista de vertices visitados.
Resposta correta: b) Um vetor de distancias minimas.
Explicacao: A tabela de distancias no algoritmo de Dijkstra e geralmente implementada como um
vetor que armazena as distancias minimas de cada vertice em relacao ao vertice de origem.
No caso de um grafo totalmente conectado e ponderado, o algoritmo de Dijkstra pode ser usado
para calcular o caminho mais curto entre dois vertices?
a) Nao, apenas o caminho mais curto entre todos os pares de vertices pode ser calculado.
b) Sim, o algoritmo de Dijkstra pode ser usado para calcular o caminho mais curto entre dois
vertices especificos.
c) Nao, ele so calcula o caminho mais curto de um vertice para todos os outros.
d) Sim, mas e mais eficiente usar o algoritmo de Floyd-Warshall.
Resposta correta: b) Sim, o algoritmo de Dijkstra pode ser usado para calcular o caminho mais
curto entre dois vertices especificos.
Explicacao: O algoritmo de Dijkstra pode ser utilizado para calcular o caminho mais curto entre dois
vertices especificos em um grafo ponderado, desde que os pesos das arestas sejam nao negativos.
Quando um vertice e marcado como "visitado" no algoritmo de Dijkstra?
a) Quando ele e removido da fila de prioridade.
b) Quando ele e adicionado a fila de prioridade.
c) Quando sua distancia minima e definitivamente encontrada.
d) Quando ele e atualizado pela primeira vez.
Resposta correta: c) Quando sua distancia minima e definitivamente encontrada.
Explicacao: No algoritmo de Dijkstra, um vertice e marcado como "visitado" (ou "finalizado") quando
sua distancia minima e determinada, o que significa que nao ha mais necessidade de revisa-lo.
Se um grafo contiver um ciclo, o algoritmo de Dijkstra pode ainda ser utilizado para encontrar o
menor caminho?
a) Nao, ciclos impedem que o algoritmo de Dijkstra funcione corretamente.
b) Sim, desde que o ciclo tenha arestas com pesos nao negativos.
c) Sim, pois o algoritmo ignora ciclos.
d) Nao, o algoritmo de Dijkstra nao lida com ciclos.
Resposta correta: b) Sim, desde que o ciclo tenha arestas com pesos nao negativos.
Explicacao: O algoritmo de Dijkstra pode lidar com grafos que contem ciclos, desde que as arestas
do ciclo tenham pesos nao negativos. A presenca de ciclos nao impede que o algoritmo encontre o
menor caminho, mas ciclos com pesos negativos causariam problemas.
Qual a diferenca entre o algoritmo de Dijkstra e o algoritmo de Bellman-Ford?
a) O algoritmo de Bellman-Ford e mais eficiente que o algoritmo de Dijkstra em grafos grandes.
b) O algoritmo de Bellman-Ford pode lidar com arestas de peso negativo, enquanto o Dijkstra nao
pode.
c) O algoritmo