The following program illustrates the Shortest Path using Dijkstra Algorithm in C++:
#include <iostream.h> #include <conio.h> #define MAX_NODE 50 struct node{ int vertex; int weight; node *next; }; struct fringe_node{ int vertex; fringe_node *next; }; node *adj[MAX_NODE]; //For storing Adjacency list of nodes.int totNodes; //No. of Nodes in Graph.constint UNSEEN=1,FRINGE=2,INTREE=3; //status of node.int status[MAX_NODE];//status arr for maintaing status. fringe_node *fringe_list;//singly link listvoid createGraph(){ node *newl,*last; int neighbours; cout<<"nn---Graph Creation---nn"; cout<<"Enter total nodes in graph : "; cin>>totNodes; for(int i=1;i<=totNodes;i++){ last=NULL; cout<<"Total Neighbours of "<<i<<" : "; cin>>neighbours; for(int j=1;j<=neighbours;j++){ newl=new node; cout<<"Neighbour #"<<j<<" : "; cin>>newl->vertex; cout<<"Weight #"<<j<<" : "; cin>>newl->weight; newl->next=NULL; if(adj[i]==NULL) adj[i]=last=newl; else{ last->next = newl; last = newl; } } } } //Insert node in a fring_list at Begining.void Insert_Beg(int item){ fringe_node *newl; newl = new fringe_node; newl->vertex = item; newl->next = NULL; newl->next = fringe_list; fringe_list = newl; } //Delete element at pos position from fringe_list.void del(int pos){ //to points to previous node from where//to insertint i; fringe_node *tmp,*delnode; for(i=1,tmp=fringe_list; i < (pos-1); tmp=tmp->next,i++); delnode = tmp->next; tmp->next = tmp->next->next; delete(delnode); } void print_path(int s,int d,int parent[]){ if(d==s) cout<<" "<<s; else{ print_path(s,parent[d],parent); cout<<"-->"<<d; } } void shortestPath(){ int i,x,parent[MAX_NODE],edge_count,w,wt,v; int min_dist,y,dist[MAX_NODE],stuck; int source,destination; node *ptr1; fringe_node *ptr2; cout<<"Enter Source Node : "; cin>>source; cout<<"Enter Destination Node : "; cin>>destination; fringe_list=NULL; for(i=1;i<=totNodes;i++){ status[i]=UNSEEN; parent[i]=0; } status[source]=INTREE; dist[source]=0; x=source; stuck=0; while( (x != destination) && (!stuck)) { ptr1=adj[x]; while(ptr1!=NULL){ y=ptr1->vertex; wt=ptr1->weight; if((status[y]==FRINGE) && (dist[x]+wt < dist[y])) { parent[y]=x; dist[y] = dist[y] + wt; } elseif(status[y]==UNSEEN){ status[y]=FRINGE; parent[y]=x; dist[y] = dist[y] + wt; Insert_Beg(y); } ptr1=ptr1->next; } if(fringe_list==NULL) stuck=1; else{ x=fringe_list->vertex; min_dist=dist[x]; ptr2=fringe_list->next; while(ptr2!=NULL){ w=ptr2->vertex; if(dist[w] < min_dist) { x=w; min_dist=dist[w]; } ptr2=ptr2->next; } del(x); status[x]=INTREE; } } if(parent[destination]==0) cout<<"No path from "<<source<<" to "<<destination; else { cout<<"nnShortest Pathn"; print_path(source,destination,parent); } } void main(){ clrscr(); cout<<"*****Minimum Spaning Tree (MST)*****n"; createGraph(); cout<<"n===Minimum Spaning Tree===n"; shortestPath(); getch(); }