迪杰斯特拉最短路径（含路径输出）

模版：

输入

输入的第一行包含2个正整数n和s，表示图***有n个顶点，且源点为s。其中n不超过50，s小于n。

以后的n行中每行有n个用空格隔开的整数。对于第i行的第j个整数，如果大于0，则表示第i个顶点有指向第j个顶点的有向边，且权值为对应的整数值；如果这个整数为0，则表示没有i指向j的有向边。当i和j相等的时候，保证对应的整数为0。

输出

只有一行，共有n-1个整数，表示源点至其它每一个顶点的最短路径长度。如果不存在从源点至相应顶点的路径，输出-1。

请注意行尾输出换行。

样例输入

4 1
0 3 0 1
0 0 4 0
2 0 0 0
0 0 1 0

#include<stdio.h>
#include<string.h>
#define inf 99999999
int map[60][60],book[60],p[60],dis[60];
//p数组用来记录s点到各个点的路径，例如，p[i]的值为结点i的上一步。 
void putlu(int u,int v)
{
	//通过v结点的上一结点查找到u结点，将路径存到栈s中，最后输出。 
	int s[60],k,i,l;
	k=0;
	l=p[v];
	while(l!=u)
	{
		s[k++]=l;
		l=p[l];
	}
	printf("%d",u);
	for(i=k-1;i>=0;i--)
		printf("--->%d",s[i]);
	printf("--->%d\n",v);
}
int main()
{
	int n,s,min,i,j,u,v;
	scanf("%d%d",&n,&s);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			scanf("%d",&map[i][j]);
			if(i!=j&&map[i][j]==0)
				map[i][j]=inf;
		}
	memset(book,0,sizeof(book));
	memset(p,-1,sizeof(book));
	for(i=0;i<n;i++)
	{
		dis[i]=map[s][i];
		if(dis[i]!=inf)//若结点s可以到达结点i则p[i]为s。说明i结点可以通过结点s到达。 
			p[i]=s;
	}
	book[s]=1;
	for(i=0;i<n;i++)
	{
		min=inf;
		for(j=0;j<n;j++)
		{
			if(min>dis[j]&&book[j]==0)
			{
				min=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(j=0;j<n;j++)
		{
			if(dis[j]>dis[u]+map[u][j])
			{
				dis[j]=dis[u]+map[u][j];
				p[j]=u;  //通过u结点更新j结点的最短路径，说明到达j结点的路径通过u。 
			}
		}
	}
	for(i=0;i<n;i++)
	{
		if(i==s)
			continue;
		if(dis[i]!=inf)
		{
			printf("从%d点到%d点的最短路径为：\n",s,i);
			putlu(s,i);		//输出路径 
			printf("长度为：%d\n\n\n",dis[i]);
		}
		else
		{
			printf("不能从%d点到%d点。\n"); 
		}
	}
	return 0;
}