Algoritmo de Caminho minimo: Algoritmo de Dijkstra em Python
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.
O algoritmo de Dijkstra funciona através da construção de uma árvore de caminho mínimo. Ele começa com um vértice inicial e, em seguida, explora todos os seus vizinhos, atualizando o custo para alcançar cada um deles. Em seguida, o algoritmo seleciona o vértice com o custo mais baixo e repete o processo. Dessa forma, ele constrói uma árvore de caminho mínimo que representa o caminho mais curto para cada vértice no grafo em relação ao vértice inicial.
Vamos entender melhor com um exemplo de implementação:
Suponha que temos um grafo ponderado com os seguintes vértices e arestas:
Vértices: A, B, C, D, E
Arestas: (A,B,3), (A,C,2), (B,C,1), (B,D,5), (C,D,3), (C,E,6), (D,E,4)
Esse video é um breve resumo, abordando apenas os conceitos iniciais porem, claro o suficiente para uma noção do Algoritmo.
Espero que tenham gostado.