Program to solve single-source shortest path problem using Dijkstra’s algorithm

// program to solve single source shortest path problem
//using dijkstra's algorithm

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

#define infinity 32767

class graph
{
	int cost[20][20],n,dist[20],s[20],a[20][20];

	public:
		void setdata();
		void getdata();
		void path(int);
};

void graph::setdata()
{
	int i,j,k;

	cout<<"\nEnter number of nodes: ";
	cin>>n;

	cout<<"\nEnter Adjacency Matrix: ";
	for(i=1;i<=n;i++)
	{
		cout<<"\nEnter "<<i<<"row :";
		for(j=1;j<=n;j++)
			cin>>a[i][j];
	}

	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			if(i==j)
				cost[i][i]=0;
			else if (a[i][j]!=0)
			{
				cout<<"\nEnter cost from "<<i<<" to "<<j<<":";
				cin>>cost[i][j];
			}
			else
				cost[i][j]=infinity;
	}

}

void graph::getdata()
{
	int i;

	for(i=1;i<=n;i++)
		if(dist[i]==32767)
			cout<<"not reachable";
		else
			cout<<dist[i]<<"\t";
}

void graph::path(int v)
{
	int i,j,min,u;

	for(i=1;i<=n;i++)
	{
		s[i]=0;
		dist[i]=cost[v][i];
	}

	s[v]=1;
	dist[v]=0;


	for(i=2;i<=n;i++)
	{
		min=32767;
		for(j=1;j<=n;j++)
			if(s[j]==0 && dist[j]<min)
				u=j;
		s[u]=1;

		for(j=1;j<=n;j++)
			if(s[j]==0 && a[u][j]==1)
				if(dist[j]>dist[u]+cost[u][j])
					dist[j]=dist[u]+cost[u][j];
	}
}

void main()
{
	graph g;
	int v;
	clrscr();

	g.setdata();

	cout<<"\nEnter the source vertex: ";
	cin>>v;
	g.path(v);

	cout<<"\nShortest paths from " << v <<" are: \n\n";
	g.getdata();

	getch();
}