Algoritmo de Dijkstra Flashcards
Qual é o objetivo principal do Algoritmo de Dijkstra?
Encontrar o caminho mais curto de um vértice de origem para todos os outros vértices em um grafo ponderado.
Qual estrutura de dados é usada para selecionar o próximo vértice a ser processado no Algoritmo de Dijkstra?
Fila de prioridade (min-heap).
O Algoritmo de Dijkstra funciona com grafos que possuem arestas de peso negativo?
Não, ele não lida corretamente com arestas de peso negativo.
O que significa “relaxar uma aresta” no contexto do Algoritmo de Dijkstra?
Atualizar a menor distância conhecida para um vértice se um caminho mais curto for encontrado.
Como o Algoritmo de Dijkstra inicia o processo de busca pelo caminho mais curto?
Inicializa a distância do vértice de origem para ele mesmo como 0 e para todos os outros vértices como infinito.
Qual é o primeiro passo após inicializar as distâncias no Algoritmo de Dijkstra?
Inserir o vértice de origem na fila de prioridade.
O que acontece quando um vértice é retirado da fila de prioridade no Algoritmo de Dijkstra?
Ele é adicionado à árvore de caminhos mais curtos, e todas as arestas que saem desse vértice são relaxadas.
O que significa a notação (distTo[]) no Algoritmo de Dijkstra? .
Representa a menor distância conhecida do vértice de origem para cada vértice
O que significa a notação (edgeTo[]) no Algoritmo de Dijkstra?
Representa a última aresta no caminho mais curto conhecido para cada vértice.
Quando o Algoritmo de Dijkstra termina sua execução?
Quando a fila de prioridade está vazia, ou seja, quando todas as distâncias mais curtas foram determinadas
- Pergunta: O que deve ser feito se uma distância menor for encontrada durante a relaxação de uma aresta?
Atualizar o valor em (distTo[]) e inserir ou atualizar o vértice na fila de prioridade.
Por que o Algoritmo de Dijkstra não funciona corretamente com arestas de peso negativo?
Porque ele assume que uma vez que um vértice é processado, a menor distância para ele foi encontrada, o que não é verdadeiro se existirem arestas de peso negativo.
Qual é a estrutura básica do grafo usada no Algoritmo de Dijkstra?
Um grafo dirigido e ponderado.
Quais são os elementos essenciais armazenados para cada vértice no Algoritmo de Dijkstra?
A menor distância conhecida ((distTo[])) e a aresta anterior no caminho mais curto ((edgeTo[])).
