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.

External links

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