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.
A tabela a seguir apresenta algumas cidades localizadas na região norte do estado do Paraná. Você pode verificar o resultado da aplicação do algoritmo de Dijkstra para a obtenção do caminho mínimo para o deslocamento entre algumas das cidades que compõem a 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.
Analisando os dados da tabela e a explicação apresentada, assinale a conclusão correta:
Alternativas
Alternativa 1:
A menor distância entre as cidades de Maringá e Londrina é de 99 km.
Alternativa 2:
O menor caminho entre as cidades de Maringá e Campo Mourão é de 91 km.
Alternativa 3:
Para percorrer o menor caminho entre a cidade de Sarandi e a cidade de Mandaguari, terá que se deslocar 31 km.
Alternativa 4:
Para percorrer o menor caminho entre as cidades de Maringá e Londrina, obrigatoriamente deverá passar na cidade de Floresta.
Alternativa 5:
Para percorrer o menor caminho entre as cidades de Maringá e Londrina, deverá se deslocar na sequência Maringá, Sarandi, Mandaguari, Londrina.
Anexos:
Soluções para a tarefa
Respondido por
0
Resposta:
Alternativa 4
Explicação:
Perguntas interessantes