#include<stdio.h>
#include<conio.h>
#define MAX_NODES 100
#define INFINITY 500

int n,dist[MAX_NODES][MAX_NODES];
shortest_path(int s,int t,int path[])
{
	struct state
	{
		int predecessor;
		int length;
		enum {permanent, tentative label;}
	}state[MAX_NODES];
	int i,k,min;
	struct state *p;
	for(p=&state[0]; p<state[n];p++)
	{
		p->predecessor=-1;
		p->length=INFINITY;
		p->label=tentative;
	}
	state[t].length=0; state[t].label=permanent;
	k=t;
	do
	{
		for(i=0;i<n;i++)
		if(dist[k][i]!=0 && state[i].label==tentative)
		{
			if(state[k].length + dist[k][i] < state[i].length)
			{
				state[i].predecessor=k;
				state[i].length=state[k].length + dist[k][i];
			}
		}
		k=0;
		min=INFINITY;
		for(i=0;i<n;i++)
		if(state[i].label==tentative && state[i].length < min)
		{
			min=state[i].length;
			k=i;
		}
		state[k].label=permanent;
	}
	while(k!=5);
	i=0;k=5;
	do
	{
		path[i++]=k;
		k=state[k].predecessor;
	}while(k>=0);
	return i;
}
void main()
{
	int s,t,p[10];
	int n,j;
	clrscr();
	printf("\nEnter the Number of Nodes in the Graph\n");
	scanf("%d",&n);
	printf("\nEnter the source code\n");
	scanf("%d",&s);
	printf("\nEnter the target node:\n");
	scanf("%d",&t);
	clrscr();
	for(i=0;i<n;i++)
	for(j=i;j<n;j++)
	{
		if(i==j)
		dist[i][j]=dist[j][i]=0;
		else
		{
			printf("\nEnetr the Distance bertween %d node and %d\n",i++,j++);
			scanf("%d",%dist[i][j]);
			dist[j][i]=dist[i][j];
		}
	}
	printf("\nTh Shortest Path is\n");
	for(i=0;i<=j;i++)
		printf("%d ->",p[i]+1);
	getch();
}