O algoritmo de Dijkstra assemelha-se ao algoritmo de busca em largura. O algoritmo de Dijkstra leva
em consideração uma matriz de custos. Cada entrada na matriz tem armazenado o custo (peso) da aresta entre dois vértices. Durante a visita aos vértices adjacentes, o programa inclui na fila apenas os vértices de menor custo. O algoritmo de Dijkstra é muito utilizado em situações em que é preciso minimizar custos ou otimizar recursos. Oliveira, P. M.; Pereira, R. de L. Estrutura de Dados I. Maringá-Pr.: Unicesumar, 2019.A tabela a seguir apresenta alguns aeroportos internacionais localizados na região sul do Brasil. Você pode verificar o resultado da aplicação do algoritmo de Dijkstra para a obtenção do caminho mínimo para o custo (em milhares) entre alguns desses aeroportos que compõem o conglomerado aeroviário da região.
Considere que o algoritmo pega como entrada um grafo orientado ponderado e um vértice de origem, passando a construir progressivamente um grafo no qual os diferentes vértices são classificados por ordem crescente de sua distância mínima em relação ao nó inicial. Considere o grafo não orientado, ou seja, é possível fazer o caminho de ida e volta entre os caminhos dos aeroportos .
Analisando os dados da tabela e a explicação apresentada, assinale a conclusão correta:
Alternativas
Alternativa 1:
O menor custo entre os aeroportos Afonso Pena e de Pelotas é de R$ 91.000.
Alternativa 2:
O menor custo entre os aeroportos Afonso Pena e Salgado Filho é de R$ 99.000.
Alternativa 3:
Para alcançar o menor custo operacional entre os aeroportos de Foz do Iguaçu e de Florianópolis, terá que investir R$ 31.000.
Alternativa 4:
Para obter o menor custo operacional entre os aeroportos Afonso Pena e Salgado Filho, obrigatoriamente deverá fazer uma conexão no aeroporto de Navegantes.
Alternativa 5:
Para chegar ao menor custo partindo do aeroporto Afonso Pena e pousando no aeroporto Salgado Filho, deverá fazer as seguintes conexões: Afonso Pena - Foz do Iguaçu - Florianópolis - Salgado Filho.
Kauany está aguardando sua ajuda, Clique aqui para responder.