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. Cidade Distância Caminho Maringá 0 - Sarandi 9 Maringá Mandaguari 23 Sarandi Floresta 34 Sarandi Campo Mourão 60 Floresta Londrina 73 Mandaguari 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: