数据结构课程设计---------最少换车次数问题

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define INFINITY 9999
#define MAXVNUM 30
char ans;
typedef struct
{
	int Vnum;
	int arcs[MAXVNUM][MAXVNUM];            //图的存储结构为邻接矩阵
}Graph;

int createGraph(Graph *g,int *start,int *end)
{
	int n,m,i,j,k,s,count;
	int t[MAXVNUM];
	printf("
★ 请输入公交车站数和公交车数:
");
	scanf("%d %d",&n,&m);
	if(n<=1 || m<1)
		return -1;
	g->Vnum = n;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			g->arcs[i][j] = INFINITY;    //邻接矩阵初始化
	for(s=0;s<m;s++)
	{
		printf("
▲请输入第%d辆公交车所途经各站的编号【0<=编号<=%d,-1结束】:
",s+1,n-1);
		scanf("%d",&k);
		count = 0;
		while(k!=-1)
		{
			t[count++]=k;
			scanf("%d",&k);
		}
		for(i=0;i<count-1;i++)
		{
			for(j=i+1;j<count;j++)        //当前线路中，从t[i]到t[j]有直达公交车
				g->arcs[t[i]][t[j]]=1;
		}
	}
	printf("
★ 请输入上车站编号和下车站编号【0<=编号<=%d】:
",n-1);
	scanf("%d%d",start,end);
	if( *start<0 || *start>n-1 || *end<0 || *end>n-1)
		return -1;
	return 0;
}
int findMinmum(Graph g,int start,int end)   //迪杰斯特拉算法找最小上车次数
{
	int s[MAXVNUM];
	int i,j,u,*dist,min;
	if(start==end)
		return 0;
	dist=(int *)malloc(sizeof(int));
	if(dist==NULL)
		return -1;
	for(i=0;i<g.Vnum;i++)
	{
		dist[i]=g.arcs[start][i];    //从start可直达的站点上车次数置1
		s[i]=0;       //所有站点的上车次数还未找到
	}
	s[start]=1;   //已经找到站点start的最少上车次数
	dist[start]=0;   //从站点start到start的最少上车次数初始化为0
	for(i=0;i<g.Vnum;++i)
	{
		min=INFINITY;
		u=start;
		for(j=0;j<g.Vnum;++j)  //u是从start出发能够到达的所有站点中上车次数最少者
		{
			if(s[j]==0 && dist[j]<min)
			{
				min=dist[j];
				u=j;
			}
		}
		s[u]=1;    //已经找到从站点start到u的最少上车次数，将u加入集合s
		for(j=0;j<g.Vnum;++j)   //更新当前情况下其他站点的最少上车次数
		{
			if(s[j]==0 && min+g.arcs[u][j]<dist[j])
				dist[j]=min+g.arcs[u][j];
		}
	}
	return dist[end];
}

int main(void)
{
	int start,end,m;
	printf("
说明：");
	printf("
	您好！欢迎使用该系统！
");
	printf("	[一]  本系统是根据有向图创建的，请先输入你想乘车地点到目的地共有多少站和该地点的公交车数量。站数相当于有向图中的顶点数。
");
	printf("	[二]  请输入每条公交车所路径的站点，相当于有向图中连接每条边的顶点。输入完后按-1进入下一辆公交车的路径。
 ");
	printf("	[三]  请输入上车地点的站编号和下车站的编号，相当于有向图中任意的两个顶点。输入完后系统将会根据所输入的信息输出最少换车次数。
 ");
	do
	{
		Graph G;
		if(createGraph(&G,&start,&end)==-1)
		{
			printf("
     真遗憾!
    创建有向图失败!   
    请重新输入数据 !
");
			return 0;
		}
		m=findMinmum(G,start,end);
		if(m<INFINITY)
			printf(" 恭喜!
  有车可以到达该目的地
  从上车站%d到下车站%d的最少换车次数为：  %d
",start,end,m-1);
		else
			printf("
对不起!
没有相应的公交车可以到达该站点 !
");
		printf("
是否继续呢(y/n)?");
		fflush(stdin);
		ans=getchar();
		system("cls");
	}while(ans==y || ans==Y);
	printf("
-----------------------谢谢你使用该系统！----------------------------");
	system("pause");
	return 0;
}