最小换乘.txt

利用dijkstra算法编写的公交线路的最小换乘问题的算法

#include<stdio.h>
#define MAX 100
#define MAXV 100
#define MAXE 100
typedef struct				/*n个车站*/
{
	int edges[MAXV][MAXV];
	int n;
}MGraph;
typedef struct node			/*第stop个车站，link指向下个车站*/
{
	int stop;
	struct node *link;
}Snode;
int dijkstra(MGraph *g,int k)		/*dijkstra算法*/
{					/*返回k点到n-1点的最短路径*/
	int i,j,p,wm;
	int pre[MAXV],dist[MAXV];
	for(i=0;i<g->n;i++)
	{
		dist[i]=g->edges[k][i];
		if(dist[i]<MAX)
			pre[i]=k;
		else
			pre[i]=-1;
	}
	pre[k]=-1;
	dist[k]=0;
	g->edges[k][k]=1;
	for(j=0;j<g->n-1;j++)
	{
		wm=MAX;
		p=-1;
		for(i=0;i<g->n;i++)
			if((g->edges[i][i]==0)&&(dist[i]<wm))
			{
				p=i;
				wm=dist[i];
			}
		if(p==-1)
			break;
		else
		{
			g->edges[p][p]=1;
			for(i=0;i<g->n;i++)
				if(g->edges[i][i]==0)
					if(dist[p]+g->edges[p][i]<dist[i])
					{
						dist[i]=dist[p]+g->edges[p][i];
						pre[i]=p;
					}
		}
	}
	return dist[g->n-1];
}
void insertlist(Snode *head,int a)		/*把车站a加入该线路中*/
{						/*节点按倒序存放*/	
	Snode *p;
	p=(Snode*)malloc(sizeof(Snode));
	p->stop=a;
	p->link=head->link;			/*加到头节点之后*/
	head->link=p;
}
void main()
{
	MGraph Graph;
	Snode *line[MAXE],*p,*q;
	int temp,i,j,m,n;
	printf("Input amount of line:");
	scanf("%d",&m);				/*m条线路*/
	printf("Input amount of stop:");
	scanf("%d",&n);				/*n个车站*/
	Graph.n=n;
	printf("Input stop of line:\n");
	for(i=0;i<m;i++)
	{
		line[i]=(Snode*)malloc(sizeof(Snode));	/*生成各线路的头节点*/
		line[i]->stop=-1;
		line[i]->link=NULL;
	}
	i=0;
	j=0;
	do
	{
		if(j==0)
		{
			printf("%d:",i+1);
			j=1;
		}
		scanf("%d",&temp);
		if(temp==-1)				/*当输入-1时，转到输下一条线路*/
		{
			i++;
			j=0;
		}
		else
			insertlist(line[i],temp);	/*将temp站加到line[i]中*/
	}while(i<m);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			Graph.edges[i][j]=MAX;
		}
	for(i=0;i<m;i++)			/*在线路line[i]上后节点到前节点的edges置一*/
		for(p=line[i]->link;p!=NULL;p=p->link)
			for(q=p->link;q!=NULL;q=q->link)
				Graph.edges[q->stop-1][p->stop-1]=1;
	for(i=0;i<n;i++)
		Graph.edges[i][i]=0;
	temp=dijkstra(&Graph,0);		/*调用dijkstra算法*/
	if(temp<MAX)
		printf("Least:%d\n",temp-1);	/*输出最小换乘次数*/
	else
		printf("Can not reach!");	/*若所经过的站数大于MAX说明从起点到不了终点*/
	getch();
	for(i=0;i<m;i++)			/*释放各线路的节点*/
		for(p=line[i];p->link!=NULL;p=p->link)
			free(p);
}