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

深藏阁楼爱情的钟 2022-02-24 01:26 359阅读 0赞

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

### 模版： ###

### 输入 ###

输入的第一行包含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;
    }