最短路径.c

最短路径 c语言 源程序 可以运行 OK

#include<stdio.h>
void dijkstra(int s[],int v,int a[][20],int n,int dist[],int prev[]){
	int i,j,MAX_VAlUE=500,u,temp;
	if(v<1||v>n) 
		return;
	for(i=1;i<=n;i++)	
	{
		dist[i]=a[v][i]; 
		s[i]=0;
		if(dist[i]==MAX_VAlUE)	
			prev[i]=0;
		else		
			prev[i]=v;
	}
	dist[v]=0;
	s[v]=1;
	for(i=1;i<n;i++)
	{
		u=v; 
		temp=MAX_VAlUE;
		for(j=1;j<=n;j++)
		    if ((!s[j]) && (dist[j]<temp))  
			{
				u=j; 
				temp=dist[j];  
			} 	
		s[u]=1;
		for(j=1;j<=n;j++)
		    if ((!s[j]) && (a[u][j]<MAX_VAlUE))
		    	if(dist[u]+a[u][j]<dist[j])
				{ 
					dist[j]=dist[u]+a[u][j];
				    prev[j]=u;
				}
	}
}	
void printpath(int dist[],int prev[],int s[],int v,int n)
{
	int i,k,u=0;
	for(i=1;i<=n;i++)
	   if(s[i]==1)  
	   {
		k=i;
		while(k!=v)	
		{
		     printf("%d<-",k);
             k=prev[k];
		}
		printf("%d ",k);
		printf(" %d ",dist[i]);
		printf("\n");
	   }		
}

void main()
{
int dist[20],v,n,s[20], prev[20],a[20][20];
int f[20][20],maxint=500,i,j;
printf("请输入节点的个数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
	   f[i][j]=0;
printf("请输入路径i,j:");
scanf("%d,%d",&i,&j);

while(i!=0 && j!=0)
{
	printf("请输入路径的大小:");
    scanf("%d",&a[i][j]);
    f[i][j]=1;
    printf("请输入路径i,j:");
    scanf("%d,%d",&i,&j);
}
for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
	   if(f[i][j]==0)
         a[i][j]=maxint;
printf("请输入源节点:");
scanf("%d",&v);
dijkstra(s,v,a,n,dist,prev);
printpath(dist,prev,s,v, n);



}