algoritmo de Dijkstra


Dado um grafo ponderado direcionado ou não direcionado com n vértices e m arestas. Os pesos de todas as arestas são não negativos. Alguns vértices iniciais são especificados. Você precisa encontrar os comprimentos dos caminhos mais curtos do vértice s para todos os outros vértices e também fornecer uma maneira de imprimir os próprios caminhos mais curtos.
 
Este problema é chamado de "problema de caminho mais curto de fonte única" (problema de caminhos mais curtos de fonte única).

Executa as mesmas tarefas que 1-K BFS, mas sem considerar K. Além disso, como 1-K BFS, ele não lida adequadamente com arestas negativas

Algoritmo:
O próprio algoritmo de Dijkstra consiste em N iterações. Na próxima iteração, o vértice V  com a menor distância a ele entre os vértices ainda não marcados, esse vértice se torna marcado e a partir dele ocorrem relaxações de vértices vizinhos.


 o comportamento assintótico final do algoritmo é: O(n2+ m)

Training problem

Dijkstra: O Começo (C++)

Training problem

Dijkstra

Como o comportamento assintótico da implementação ingênua do algoritmo de Dijkstra é: \(O(n^2 + m)\), à medida que o número de vértices aumenta, a velocidade de trabalho torna-se insatisfatória.
 Várias estruturas de dados podem ser usadas para melhoria: Pilhas de Fibonacci, conjuntos set ou uma fila de prioridade priority_queue. 
Considere um exemplo com conjunto, como resultado, a assintótica final é: \(O(n log (m))\) , detalhes.

Training problem

Algoritmo de Dijkstra em O(M logN) conjunto c: Start (C++)