Dijkstra's algorithm


Given a directed or undirected weighted graph with n vertices and m edges. The weights of all edges are non-negative. Some starting vertex s is specified. You need to find the lengths of the shortest paths from vertex s to all other vertices, and also provide a way to print the shortest paths themselves.
 
This problem is called the "single source shortest path problem" (single-source shortest paths problem).

Performs the same tasks as 1-K BFS, but without regard to K. Also, like 1-K BFS, it does not properly handle negative edges

Algorithm:
Dijkstra's algorithm itself consists of N iterations. At the next iteration, the vertex V  with the smallest distance to it from among the vertices not yet marked, this vertex becomes marked and relaxations of neighboring vertices occur from it.


 final asymptotic behavior of the algorithm is: O(n2+ m)

Training problem

Dijkstra: The Beginning (C++)

Training problem

Dijkstra

Since the asymptotic behavior of the naive implementation of Dijkstra's algorithm is: \(O(n^2 + m)\), then as the number of vertices increases, the speed of work becomes unsatisfactory.
 Various data structures can be used for improvement: Fibonacci heaps, set sets, or a priority queue priority_queue. 
Consider an example with set, as a result, the final asymptotics is: \(O(n log (m))\), details.

Training problem

Dijkstra's algorithm in O(M logN) c set: Start (C++)