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 vertices em um grafo.
b) Encontrar o caminho mais curto entre um vertice de origem e todos os outros vertices.
c) Ordenar os vertices de um grafo.
d) Detectar ciclos em um grafo.
Resposta explicativa: O algoritmo de Dijkstra e utilizado para determinar o caminho de menor custo
ou distancia a partir de um vertice de origem para todos os outros vertices em um grafo com pesos
nao negativos.
Qual e a principal restricao dos pesos das arestas para que o algoritmo de Dijkstra funcione
corretamente?
a) Todos os pesos devem ser positivos ou zero.
b) Os pesos podem ser negativos.
c) Nao ha restricao para os pesos.
d) Os pesos devem ser inteiros pares.
Resposta explicativa: O algoritmo de Dijkstra nao funciona corretamente com arestas de peso
negativo, pois ele assume que uma vez que um vertice foi visitado, seu menor caminho foi
encontrado.
Qual estrutura de dados e comumente usada para selecionar o vertice de menor distancia ainda
nao visitado em Dijkstra?
a) Pilha
b) Fila
c) Fila de prioridade (Heap)
d) Lista encadeada
Resposta explicativa: Uma fila de prioridade (geralmente implementada como um heap) permite
acessar rapidamente o vertice com a menor distancia estimada, otimizando a eficiencia do
algoritmo.
No algoritmo de Dijkstra, o que significa "distancia inicial infinita"?
a) Que o vertice nao existe no grafo.
b) Que inicialmente nao ha caminho conhecido do vertice de origem ate ele.
c) Que a distancia e zero.
d) Que o vertice ja foi visitado.
Resposta explicativa: Inicialmente, todos os vertices sao atribuidos uma distancia infinita para
indicar que ainda nao foi encontrado nenhum caminho a partir da origem.
Durante a execucao do algoritmo de Dijkstra, o que acontece quando um vertice e marcado como
"visitado"?
a) Ele e removido do grafo.
b) Sua distancia final e determinada e nao sera atualizada novamente.
c) Ele passa a ter distancia infinita.
d) Ele e colocado de volta na fila de prioridade.
Resposta explicativa: Uma vez que um vertice e visitado, seu menor caminho da origem foi
confirmado, e ele nao precisa mais ser revisitado.
Qual e o papel da operacao de "relaxamento" no algoritmo de Dijkstra?
a) Reduzir a complexidade do grafo.
b) Atualizar a distancia de um vertice vizinho se um caminho mais curto for encontrado.
c) Remover vertices com peso negativo.
d) Ordenar as arestas do grafo.
Resposta explicativa: Relaxar uma aresta significa verificar se o caminho atual ate um vertice pode
ser melhorado passando por outro vertice e atualizar a distancia se necessario.
Considere um grafo com 5 vertices e conexoes ponderadas. Qual e a complexidade do algoritmo de
Dijkstra quando implementado com uma fila de prioridade baseada em heap binario?
a) O(V2)
b) O(V + E log V)
c) O(E + V log V)
d) O(V!)
Resposta explicativa: Com um heap binario, a complexidade e O((V + E) log V), pois cada operacao
de insercao ou extracao da fila de prioridade tem custo logaritmico, aplicado para vertices e arestas.
Se aplicarmos o algoritmo de Dijkstra em um grafo nao direcionado, com pesos positivos, o
algoritmo:
a) Nao funcionara.
b) Funcionara normalmente.
c) Vai detectar ciclos.
d) Vai alterar os pesos das arestas.
Resposta explicativa: O algoritmo funciona normalmente em grafos nao direcionados, desde que os
pesos das arestas sejam nao negativos, pois a direcao nao afeta o calculo do menor caminho.
Em um grafo com 4 vertices conectados por arestas de pesos 1, 2, 3 e 4, iniciando pelo vertice A,
qual vertice tera a menor distancia inicial atribuida durante a primeira iteracao?
a) O vertice com peso 1.
b) O vertice com peso 4.
c) O vertice com peso 3.
d) Todos tem distancia infinita.
Resposta explicativa: O vertice conectado diretamente a origem com o menor peso tera sua
distancia atualizada primeiro, neste caso o vertice com aresta de peso 1.
Qual e o efeito de arestas de peso zero no algoritmo de Dijkstra?
a) Sao ignoradas pelo algoritmo.
b) Permitem caminhos alternativos sem alterar a distancia final minima.
c) Podem causar loops infinitos.
d) Tornam o algoritmo invalido.
Resposta explicativa: Arestas de peso zero sao permitidas e podem fornecer caminhos alternativos
sem aumentar a distancia minima; o algoritmo continua funcionando corretamente.
Em um grafo onde dois caminhos diferentes tem a mesma soma de pesos, como o algoritmo de
Dijkstra decide qual caminho armazenar?
a) Sempre escolhe o caminho mais longo.
b) Armazena o primeiro caminho encontrado com aquela distancia minima.
c) Calcula uma media entre os dois caminhos.
d) Descarta ambos os caminhos.
Resposta explicativa: Dijkstra armazena o primeiro caminho que alcanca a distancia minima para o
vertice; se outro caminho com mesma distancia for encontrado, normalmente nao altera o registro,
a menos que o algoritmo seja adaptado para multiplos caminhos.
Qual das alternativas abaixo e verdadeira sobre a aplicacao do algoritmo de Dijkstra em grafos com
arestas negativas?
a) Ele encontra o caminho mais curto corretamente.
b) Ele pode produzir resultados incorretos.
c) Ele ignora arestas negativas.
d) Ele transforma pesos negativos em positivos automaticamente.
Resposta explicativa: Dijkstra nao funciona corretamente com arestas de peso negativo, pois
assume que uma vez visitado, o menor caminho esta certo, o que nao e garantido se houver
reducao posterior pelo peso negativo.
Durante a execucao do algoritmo, como sao atualizadas as distancias dos vertices vizinhos do
vertice atual?
a) Somando a distancia do vertice atual ao peso da aresta que conecta o vizinho.
b) Multiplicando a distancia do vertice atual pelo peso da aresta.
c) Mantendo a distancia original sem alteracao.
d) Atribuindo zero a distancia do vizinho.
Resposta explicativa: Para cada vizinho do vertice atual, calcula-se a distancia total passando por
ele somando a distancia acumulada ate o vertice atual com o peso da aresta que leva ao vizinho, e
atualiza-se se essa distancia for menor.
Qual e a diferenca entre Dijkstra e o algoritmo de Bellman-Ford?
a) Dijkstra funciona com pesos negativos; Bellman-Ford nao.
b) Dijkstra nao funciona com pesos negativos; Bellman-Ford funciona.
c) Ambos tem a mesma complexidade.
d) Bellman-Ford so funciona em grafos direcionados.
Resposta explicativa: O algoritmo de Bellman-Ford pode lidar com arestas de peso negativo,
enquanto Dijkstra nao, tornando Bellman-Ford mais flexivel em grafos com custos negativos.
Qual das seguintes operacoes e essencial no passo principal do algoritmo de Dijkstra?
a) Selecionar o vertice com maior grau.
b) Selecionar o vertice de menor distancia ainda nao visitado.
c) Ordenar todas as arestas.
d) Remover vertices isolados.
Resposta explicativa: O passo crucial do algoritmo e escolher o vertice com a menor distancia
conhecida ainda nao visitado, pois garante que o caminho minimo ate ele foi encontrado.
O que acontece se o algoritmo de Dijkstra for iniciado em um vertice que nao esta conectado a
nenhum outro vertice?
a) Todas as distancias permanecem infinitas, exceto para a origem.
b) O algoritmo gera erro.
c) Ele conecta automaticamente os vertices.
d) Todas as distancias se tornam zero.
Resposta explicativa: Se o vertice de origem nao tem conexoes, nao ha caminhos possiveis,
portanto as distancias de todos os outros vertices permanecem infinitas, e a distancia da origem e
zero.
Qual e a utilidade pratica do algoritmo de Dijkstra em sistemas de navegacao?
a) Ordenar pontos de interesse.
b) Encontrar rotas mais curtas entre dois locais.
c) Calcular areas de terreno.
d) Identificar ruas sem saida.
Resposta explicativa: O algoritmo e amplamente utilizado para calcular rotas de menor distancia ou
custo em mapas e sistemas de GPS, garantindo o trajeto mais eficiente entre locais.
Quando um vertice e retirado da fila de prioridade no algoritmo de Dijkstra, qual informacao sobre
elee considerada definitiva?
a) Seu grau no grafo.
b) A distancia minima da origem ate ele.
c) O numero de arestas incidentes.
d) Seu valor de cor no grafo.
Resposta explicativa: Ao ser retirado da fila de prioridade, o vertice tem sua menor distancia da
origem finalizada, pois nao existem caminhos mais curtos possiveis restantes.
Qual e o efeito de atualizar repetidamente as distancias dos vizinhos durante a execucao do
algoritmo de Dijkstra?
a) Garante que todos os caminhos possiveis sejam testados para encontrar o menor.
b) Cria loops infinitos.
c) Diminui a precisao do calculo.
d) Remove vertices do grafo.
Resposta explicativa: Atualizar repetidamente os vizinhos (relaxamento) assegura que o algoritmo
considere todas as opcoes para cada vertice, garantindo que o caminho mais curto seja
encontrado.
Em termos de armazenamento, qual informacao adicional alem da distancia minima e geralmente
mantida em cada vertice para reconstruir o caminho mais curto?
a) O grau do vertice.
b) O vertice predecessor no caminho minimo.
c) O numero de vizinhos.
d) O tempo de execucao do algoritmo.
Resposta explicativa: Para reconstruir o caminho mais curto do vertice de origem a qualquer outro,
armazena-se para cada vertice seu predecessor, permitindo percorrer o caminho inversamente.
Se desejar, posso continuar a lista com mais 30 perguntas detalhadas sobre o algoritmo de Dijkstra,
atingindo facilmente 1000 palavras ou mais com explicacoes detalhadas para cada questao. Quer
que eu continue?