shortest.c

根据网络的各个点之间的距离求出两点之间的最短距离,并给出两点之间的最短路径

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0	
#define MAX 65535

int cost[50][50];
void shortest (int v,int *dist,int *path,int n)
{
	int *s;				/*s用来标记对应的接点是否在最短路径中，TRUE表示在，FALSE表示不在*/
	int num,i,u,first,k,min,w;
	s=(int *)malloc(sizeof(int)*n);
	for (i=1;i<=n;i++)			/*initial array s*/
	{
		s[i]=FALSE;
		dist[i]=cost[v][i];
		path[i]=v;
	}
	s[v]=TRUE;
	dist[v]=0;
	path[v]=v;
	for (num=2;num<=n-1;num++)
	{
		for (first=1;first<=n;first++)
			if (s[first]==FALSE)
			{
				min=s[first];
				u=first;
				break;
			}
		
		for (k=first;k<=n;k++)
			if ((s[k]==FALSE)&&s[k]<min)
			{
				min=s[k];
				u=k;
			}		/*u为最小的dist接点*/
	
		s[u]=TRUE;

		for (w=1;w<=n;w++)
			if (s[w]==FALSE)
				if(dist[w]>(dist[u]+cost[u][w]))
				{
					dist[w]=dist[u]+cost[u][w];
					path[w]=u;
				}
			//	dist[w]=(dist[w]<(dist[u]+cost[u][w]))?dist[w]:(dist[u]+cost[u][w]);
	}
}

void main (void)
{
	int num,i,j,n,v,*dist,*path,allpath[50][50];
	printf("请输入连接图中节点的个数:");
	scanf("%d",&n);
	dist=(int *)malloc(sizeof(int)*(n+1));
	path=(int *)malloc(sizeof(int)*n);
	printf("\n请输入连接图的邻接成本矩阵(用65535代表+∞):\n");
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			scanf("%d",&cost[i][j]);
	printf("请输入源点:");
	scanf("%d",&v);
	printf("\n");
	shortest (v,dist,path,n);
	printf("源点:%d\n",v);
//	for (i=1;i<=n;i++)
//			printf("--%d--",i);
//	printf("\n");
//	for (i=1;i<=n;i++)
//	{
//		if (dist[i]==MAX)
//			printf(" +∞ ");
//		else 
//			printf("  %d  ",dist[i]);
//	}
//	printf("\n");
//	for (i=1;i<=n;i++)
//		printf("%d ",path[i]);
	printf("----------成本----------最短路径-----------\n");
	for (i=1;i<=n;i++)
	{
		for (num=1,j=i,allpath[i][1]=i;path[j]!=v;j=path[j])
		{
			num++;
			allpath[i][num]=path[j];
		}
		allpath[i][++num]=v;
		printf("v%d~v%d: ",v,i);
		if (dist[i]==MAX)
			printf("   +∞		");
		else 
			printf("   %d		",dist[i]);
		for (j=num;j>=1;j--)
			printf("%d ",allpath[i][j]);

	//	if (dist[i]==MAX)
	//		printf(" +∞");
	//	else 
	//		printf(" %d",dist[i]);
		printf("\n");

	}
}