Dijkstra's Algorithm in C++

[1060 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.

Dijkstra's Algorithm in C++

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); } }

Output

Distance of node1=1 Path=1<-0 Distance of node2=5 Path=2<-3<-0 Distance of node3=3 Path=3<-0 Distance of node4=6 Path=4<-2<-3<-0
Dijkstra's Algorithm and Flowchart with implementation in Java
        

Algorithm Logic Test

Our Quiz prepared by Experts Helps you identify your knowledge in Algorithms. Everyone should atleast attempt this Quiz Once. 



Need any help in Programming? Chat with Us

Comments



Online Compiler
Search
Algorithm Quiz

Only 5% Users were able to score above 75% in this Quiz. Can You Crack this?

Deals Ends in





Online Games
Play 2048 Game Online and Relax.
Play 2048 Game Online

Search Tags

    C++ program for Dijkstra