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

void main()
{
	int i, j;

	//Get vertex numbers
	int vn;
	cout<<"\n Enter vertex count: ";
	cin>>vn;

	//Cost matrix
	int cost[15][15];
	for (i=0;i<vn;i++)
	{
		for(j=0;j<vn;j++)
		{
			cost[i][j]=-1;
		}
	}

	//Get cost matrix
	cout<<"\n Enter weight of edge:\n";
	for(i=0;i<vn;i++)
	{
		for(j=0;j<vn;j++)
		{
			if(i==j)
				cost[i][j]=0;

			if(cost[i][j]==-1)
			{
				cout<<"\n "<<i<<" to "<<j<<" : ";
				cin>>cost[i][j];
			}
		}
	}

	//Displaying cost matrix
	cout<<"\n Entered Cost Matrix:";
	cout<<"\n";
	for(i=0;i<vn;i++)
	{
		for(j=0;j<vn;j++)
		{
			cout<<cost[i][j]<<" ";
		}
		cout<<"\n";
	}

	//Initializing single source
	int d[15], p[15], f[15];
	for(i=0;i<vn;i++)
	{
		d[i]=999;	//distance	->	infinity
		p[i]=-1;	//parent	->	null
		f[i]=0;		//visited	->	no
	}

	//Get starting vertex
	cout<<"\n Enter Starting vertex: ";
	int s;
	cin>>s;

	//Process staring vertex
	d[s]=0;
	p[s]=-1;
	f[s]=1;

	int c=s; 
	int temp1;
	int smallest=999;

	for(i=0;i<5;i++)
	{
			//update distances
			for(j=0;j<vn;j++)
			{
				if(cost[c][j]>0)	//Check if edge is present
				{
					if(d[j]>d[c]+cost[c][j])
					{
						d[j]=d[c]+cost[c][j];
						p[j]=c;
					}
			
				}
			}

			//Mark vertex visited
			f[c]=1;
			smallest=999;

			//Retrieve smallest vertex from remaining
			for (int k=0;k<vn;k++)
			{
				if(f[k]!=1 && d[k]<smallest)
				{
					smallest=d[k];
					c=k;
				}
			}

			smallest=999;

	}

	//Display result
	cout<<"\n Shortest Path:";
	cout<<"\n Vertex\tDist\tParent\n";
	for(i=0;i<vn;i++)
	{
		cout<<i<<"\t"<<d[i]<<"\t"<<p[i]<<"\n";
	}

	getch();
}

/* OUTPUT


 Enter vertex count: 5

 Enter weight of edge:

 0 to 1 : 10

 0 to 2 : -1

 0 to 3 : 5

 0 to 4 : -1

 1 to 0 : -1

 1 to 2 : 1

 1 to 3 : 2

 1 to 4 : -1

 2 to 0 : -1

 2 to 1 : -1

 2 to 3 : -1

 2 to 4 : 4

 3 to 0 : -1

 3 to 1 : 3

 3 to 2 : 9

 3 to 4 : 2

 4 to 0 : -1

 4 to 1 : -1

 4 to 2 : 6

 4 to 3 : -1

 Entered Cost Matrix:
0 10 -1 5 -1
-1 0 1 2 -1
-1 -1 0 -1 4
-1 3 9 0 2
-1 -1 6 -1 0

 Enter Starting vertex: 0

 Shortest Path:
 Vertex Dist    Parent
0       0       -1
1       8       3
2       9       1
3       5       0
4       7       3

*/