Question

O Algoritmo de Dijkstra (E.W. Dijkstra) é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance. Ele não garante, contudo, a exatidão da solução caso haja a presença de arcos com valores negativos. Este algoritmo parte de uma estimativa inicial para o custo mínimo e vai sucessivamente ajustando esta estimativa. Ele considera que um vértice estará fechado quando já tiver sido obtido um caminho de custo mínimo do vértice tomado como raiz da busca até ele. Caso contrário ele dito estar aberto. Conteúdo Disponível em acessado em 13/04/2022 Com base nessas informações e no estudo realizado durante a disciplina, analise o Grafo a seguir e implemente o algoritmo de Dijkstra para descobri o caminho a ser percorrido entre o nó A até E. OBS: Você deverá substituir os valores de 1 a 8 pelos digitos de seu RA. Exemplo: 21192817 -> Posição 1 = 2 Posição 2 = 1 Posição 3 = 1 Posição 4 = 9 ..... Você deverá enviar como resposta o caminho percorrido e o valor total do seu caminho. Exemplo: A -> B -> C -> D -> E = Total 15

Answer 1

Resposta:

A resposta vai depender do RA do aluno no exemplo desse RA: 21192817

o caminho mais curto a ser percorrido seria!

A -> B -> C -> D -> E = TOTAL 12

Explicação: