dijkpath.cpp

single source shortest path

/*************************************************************
  Assignment No. :-
  Title    :- Program for find out single sourcr-Shortest Path
			  for given vetix.(DIJKSTRA Algo.)
  Name     :-Amit Chaudhari
  Roll No. :- 03	
**************************************************************/

#include<iostream.h>
#include<conio.h>

class dpath
{
	int i,j,k,n,cost[10][10],dist[10],status[10];
	public:
	   void get();
	   void shortpath();
	   int mini(int,int);
	   void print();
	   void printf();
};
void dpath::get()
{
	clrscr();
	cout<<endl<<"\n Enter the no. of vertices ==> ";
	cin>>n;
	cout<<endl<<"\n Enter the cost matrics:-\n";
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			cout<<"["<<i<<"]"<<"\t"<<"["<<j<<"]"<<"\t";
			cin>>cost[i][j];
			if(cost[i][j]==0)
			{
				cost[i][j]=999;
			}
		}
	}
}
int dpath::mini(int x,int y)
{
	if(x<y)
	   return(x);
	else
	  return(y);
}
void dpath::shortpath()
{
	int source,round,min,minnode;
	cout<<"\n Enter Source Node ==> ";
	cin>>source;
	for(i=0;i<n;i++)
	{
		 dist[i]=cost[source][i];
		 status[i]=0;
	}
	status[source]=1;
	//to find min dist
	cout<<endl<<"\n Shortest Path Marix ==> "<<endl;
	for(round=1;round<n;round++)
	{
		 min=999;
		 minnode=0;
		 for(int r=0;r<n;r++)
		 {
			if(status[r]==0 && dist[r]<min)
			{
				  min=dist[r];
				  minnode=r;
			}
		 }
		 status[minnode]=1;
		 for(int c=0;c<n;c++)
		 {
			  if(status[c]==0 && cost[minnode][c]!=999)
			  {
					dist[c]=mini(dist[c],dist[minnode]+cost[minnode][c]);
			  }
		 }
	}
}
void dpath::print()
{
	for(i=0;i<n;i++)
	{
		 cout<<"\t "<<dist[i];
	}
}
void dpath::printf()
{
	int dest;
	cout<<"\n enter the destination";
	cin>>dest;
	if(dist[dest]==999)
		cout<<"\n path is not available";
	else
		cout<<"\n shortest path desination is"<<dist[dest];
}
void main()
{
	dpath s;
	s.get();
	s.shortpath();
	s.print();
	s.printf();
	getch();
}

/*

*/