Dijkstra's algorithm
 | The English used in this article or section may not be easy for everybody to understand. (April 2014) |
Dijkstra's algorithm is a graph algorithm. It 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 .
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
- 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
- Pseudocode for Dijkstra's Algorithm at English Wikipedia
- Dijkstra's Algorithm in C++