Dijkstra's algorithm

Dijkstra's algorithm , is a graph algorithm which is used to solve single-source shortest path problem for non-negative edge costs. It takes a source vertex and finds the path with lowest cost between the source vertex and every other vertex in the graph. Time complexity varies with data structure used . The implementation based on min-priority queue implemented by a Fibonacci heap has running time $O(|E|+|V|\log |V|)$.

Algorithm

Initialize distances of vertices to be infinity and that of source to be 0. Insert the source into the min-priority queue. Take the top-element of the min-priority queue and see all of its neighbours, if the distance of the neighbour using the current element is less than the previous distance of the neighbour , then update the distance and insert it into queue. Repeat this procedure till the queue gets empty.

References

• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Section 24.3: Dijkstra's algorithm". Introduction to Algorithms (Second ed.). MIT Press and McGraw–Hill. pp. 595–601. ISBN 0-262-03293-7.
• https://github.com/xtaci/algorithms/blob/master/include/dijkstra.h

Other websites

• Pseudo code - Pseudo code for Dijkstra's Algorithm
• C++ implementation Dijkstra's Algorithm in C++