Dijkstra Algorithm

Dijkstra algorithm gets its name from the Dutch computer scientist Edsger Dijkstra who invented this algorithm in 1959. It is used to find the shortest path between two non-negative nodes in a graph. Dijkstra algorithm is widely used for the purpose of routing.

For any giving node in a graph the algorithm finds the path which is the shortest from that node to all the corresponding nodes in the graph. As stated earlier also that this algorithm is used to find the shortest path between two distinct nodes on the graph, e.g., suppose there are two cities X and Y and there are three different path of going to cities Y from X, then Dijkstra algorithm finds out the shortest path between these two cities X and Y.

In the above example, the shortest path could be found on the basis of distance in Kilometers or on the basis of time taken on each path. The following figure will illustrate the example in more detail.

As the above figure shows there are three ways of going from city X to city Y. First is to take the Highway which is 25km long, second, is to take the tunnel which is 15km long and last is through city Z which is 20 km long. Now through Dijkstra algorithm we can find out that the shortest path between city X and Y is through the tunnel which is just 15km long.

But what if time was the key factor in finding out the shortest path between the two cities? Now consider the time taken on the highway, tunnel and through city Z are 1hour, 1 hour 30 min and 2 hour respectively, then the shortest path will be the highway since it take the shortest time to reach city Y.

C++ implementation

#include<stdio.h > #include<iostream.h> #include<conio.h> #include<process.h> #define MAX 10 #define TEMP 0 #define PERM 1 #define infinity 9999 int create_graph(); int findpath(int, int, int [], int *); int display(); struct node { int predecessor; int dist; /*minimum distance of node from source*/ int status; }; int adj[MAX][MAX]; int n; void main() { int i,j; int source,dest; int path[MAX]; int shortdist,count; create_graph(); cout<<"The adjacency matrix is :n"; display(); while(1) { cout<<"Enter source node(0 to quit) : "; cin>>source; cout<<"Enter destination node(0 to quit) : "; cin>>dest; if(source==0 || dest==0) exit(1); count = findpath(source,dest,path,&shortdist); if(shortdist!=0) { cout<<"Shortest distance is : "<<shortdist; cout<<"nShortest Path is : "; for(i=count;i>1;i–) cout<<path[i]; cout<<path[i]; cout<<"n"; } else cout<<"There is no path from source to destination noden"; }/*End of while*/ }/*End of main()*/ int create_graph() { int i,max_edges,origin,destin,wt; cout<<"Enter number of vertices : "; cin>>n; max_edges=n*(n-1); for(i=1;i<=max_edges;i++) { cout<<"Enter edge (0 0 to quit) : "<<i; cin>>origin; cout<<"ttt"; cin>>destin; if((origin==0) && (destin==0)) break; cout<<"Enter weight for this edge : "; cin>>wt; if( origin > n || destin > n || origin<=0 || destin<=0) { cout<<"Invalid edge!n"; i–; } else adj[origin][destin]=wt; }/*End of for*/ }/*End of create_graph()*/ int display() { int i,j; for(i=1;i<=n;i++) { for(j=1;j<=n;j++) cout<<adj[i][j]; cout<<"n"; } }/*End of display()*/ int findpath(int s,int d,int path[MAX],int *sdist) { struct node state[MAX]; int i,min,count=0,current,newdist,u,v; *sdist=0; /* Make all nodes temporary */ for(i=1;i<=n;i++) { state[i].predecessor=0; state[i].dist = infinity; state[i].status = TEMP; } /*Source node should be permanent*/ state[s].predecessor=0; state[s].dist = 0; state[s].status = PERM; /*Starting from source node until destination is found*/ current=s; while(current!=d) { for(i=1;i<=n;i++) { /*Checks for adjacent temporary nodes */ if ( adj[current][i] > 0 && state[i].status == TEMP ) { newdist=state[current].dist + adj[current][i]; /*Checks for Relabeling*/ if( newdist < state[i].dist ) { state[i].predecessor = current; state[i].dist = newdist; } } }/*End of for*/ /*Search for temporary node with minimum distand make it current node*/ min=infinity; current=0; for(i=1;i<=n;i++) { if(state[i].status == TEMP && state[i].dist < min) { min = state[i].dist; current=i; } }/*End of for*/ if(current==0) /*If Source or Sink node is isolated*/ return 0; state[current].status=PERM; }/*End of while*/ /* Getting full path in array from destination to source */ while( current!=0 ) { count++; path[count]=current; current=state[current].predecessor; } /*Getting distance from source to destination*/ for(i=count;i>1;i–) { u=path[i]; v=path[i-1]; *sdist+= adj[u][v]; } return (count); }/*End of findpath()*/

Output: