After Bellman Ford Algorithm, Dijkstra's algorithm is another one that is used in graph search for finding the shortest path. Many algorithms exist for the same problem. Let’s study about it in detail. We will recommend to try it yourself first after understanding the concept.
If you have learned about graph search, weighted and unweighted graphs, then this algorithm is easy to understand. You can use Dijkstra's algorithm in single source shortest path problem. It’s a greedy method for calculating the shortest path from a source vertex to other vertices in a graph.
It was formed by a famous computer scientist Edsger Wybe Dijsktra in 1956 and then it was published after three years. It is applied in the weighted directed or undirected graph. It exists in many types including the two that we mentioned above. While computing the shortest path from source to the other nodes, it makes a shortest path tree.
A variant of this algorithm is known as uniform cost search in Artificial Intelligence. There is an important difference to note down between Bellman and Dijkstra's algorithm. It can’t help you in dealing with negative edge weights. It will only work when all the weights are positive. Moreover, it makes the use of ordered labels that are either positive integers or real numbers.
The complete implementation of Dijkstra's algorithm in C++ is given below
Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once.