Dijkstra's Algorithm in C++

[4461 views]

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.

What is Dijkstra's Algorithm?

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.

Algorithm-

The first step is to keep the distance of vertices infinity excluding the source vertex distance. The source vertex will be zero.
Next stop involves pushing the source vertex in a min-priority queue in the form (distance, vertex)
You may have to pop the vertex keeping a minimum distance from the priority queue
Now, it’s time for updating the connected vertices distances to the popped vertex in "current vertex distance + edge weight < next vertex distance",
Again, push this vertex with updated distance to the priority queue
Keep using it even if it has been visited before
The same algorithm will be applied again
When the priority queue will become empty, then stop using this algorithm.

The complete implementation of Dijkstra's algorithm in C++ is given below

Code

#include<iostream> #include<stdio.h> using namespace std; #define INFINITY 9999 #define max 5 void dijkstra(int G[max][max],int n,int startnode); int main() { int G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{10,0,1,6,0}}; int n=5; int u=0; dijkstra(G,n,u); return 0; } void dijkstra(int G[max][max],int n,int startnode) { int cost[max][max],distance[max],pred[max]; int visited[max],count,mindistance,nextnode,i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j]==0) cost[i][j]=INFINITY; else cost[i][j]=G[i][j]; for(i=0;i<n;i++) { distance[i]=cost[startnode][i]; pred[i]=startnode; visited[i]=0; } distance[startnode]=0; visited[startnode]=1; count=1; while(count<n-1) { mindistance=INFINITY; for(i=0;i<n;i++) if(distance[i]<mindistance&&!visited[i]) { mindistance=distance[i]; nextnode=i; } visited[nextnode]=1; for(i=0;i<n;i++) if(!visited[i]) if(mindistance+cost[nextnode][i]<distance[i]) { distance[i]=mindistance+cost[nextnode][i]; pred[i]=nextnode; } count++; } for(i=0;i<n;i++) if(i!=startnode) { cout<<"\nDistance of node"<<i<<"="<<distance[i]; cout<<"\nPath="<<i; j=i; do { j=pred[j]; cout<<"<-"<<j; }while(j!=startnode); } }