graph.h

传统的Dijkstra 算法无疑是解决一般最短路径问题的最优算法

{
	int k,count=1;//count用来计算从站点a开出的线路
	////查找名为a的顶点在数组graph中的序号
	k=LocateVertex(a);
	while(k==-1)
	{
		cout<<"1找不到改点，正确格式为（S+四位整数）：";
		cin>>a;
		k=LocateVertex(a);
	}
	ARcType *p;
	p=new ARcType;
	p=graph[k].firstarc;
	if(!p)return 0;
	strcpy(s[1],p->lname);
	for(;p->nextarc;p=p->nextarc)
		if(strcmp(p->lname,p->nextarc->lname))
		{
			strcpy(s[++count],p->nextarc->lname);
		}
	return count;
}


//第二步，求进入站点a所有线路名字,复制到s[i]中
int GRaph::findpathin(ElemType s[100],ElemType a)
{
	int k,count=1;//count用来计算经过某个站点的线路
	////查找名为a的顶点在数组graph中的序号
	k=LocateVertex(a);
	while(k==-1)
	{
		cout<<"2找不到改点，正确格式为（S+四位整数）：";
			cin>>a;
		k=LocateVertex(a);
	}
	ARcType *p;
	p=new ARcType;
	p=graph1[k].firstarc;
	if(!p)return 0;
	strcpy(s[1],p->lname);
	for(;p->nextarc;p=p->nextarc)
		if(strcmp(p->lname,p->nextarc->lname))
			strcpy(s[++count],p->nextarc->lname);
	return count;
}

int GRaph::directpath(ElemType h[100],ElemType t[100],int counth,int countt)//看是否有直接路线,h,t为经过起点和终点的线路名数组
{ 
	int i,j,k,n,linenum,sta,money,time1=0,count=0;
	ARcType *p;
	for(i=1;i<=counth;i++)
		for(j=1;j<=countt;j++)
			if(strcmp(h[i],t[j])==0)
			{
             //先计算所用时间,费用
				linenum=change(h[i]);
				sta=0;
				money=0;
                k=LocateVertex(vhead);
				n=LocateVertex(vtail);
			
					for(p=graph[k].firstarc;p&&(k!=n);)
						if(strcmp(p->lname,h[i])==0)
						{
							time1+=p->time;
							k=p->adjvertex;
                           p=graph[k].firstarc;
						   sta++;
						}
						else p=p->nextarc;
						money=judgemoney(sta,ticket[linenum]);
						L[change(h[i])]=1;


				cout<<vhead<<"->"<<h[i]<<"->"<<vtail<<"   ";
				cout<<"所用时间为："<<time1<<"分钟,"<<"费用为："<<money<<"元"<<endl;
			    count++;
			}
	return count;
}


int GRaph::oncepath(ElemType h[100],ElemType t[100],int counth,int countt)//看是否有转一次车路线,即看线路i和j有没有公共的站点
{//其中counth为从起点出发的线路数，countt为进入终点的线路数
	//h[i]则记录了从起点出发的线路名，h[i]为第i条的名字
	//t[j]则记录了进入终点的线路名，t[j]为第j条的名字
	//有个问题是环行线路h[i]进入的站点不要包括起点
	int i,j,m,n,k,end,busline1,busline2,money=0,sta,tottime=0,count=0;
	ARcType *p;
	p=new ARcType;
	for(i=1;i<=counth;i++)
		for(j=1;j<=countt;j++)
			for(m=1;m<=en[change(h[i])];m++)//en[change(h[i])]为线路h[i]会进入的站点数
				for(n=1;n<=fn[change(t[j])];n++)//fn[change(t[j])]为线路t[j]会从之出发的站点数
					if((strcmp(e[change(h[i])][m],f[change(t[j])][n])==0)&&strcmp(h[i],t[j]))
					{
                         //看是分段计价还是单一票制，分段为true
						//公共站点不能是起点或终点
					  busline1=change(h[i]);
					  busline2=change(t[j]);

					  if(strcmp(e[change(h[i])][m],vhead)==0)continue;
                      if(strcmp(e[change(h[i])][m],vtail)==0)continue;
					 tottime=0;
		             sta=0;
					 money=0;
					//先求所用时间,和费用
                     k=LocateVertex(vhead);					
				     end=LocateVertex(vtail);
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(h[i])][m]);)
						 if(strcmp(p->lname,h[i])==0)//沿着h[i]走但是没有走到公共站点e[change(h[i])][m]
						 {
							tottime+=p->time;
							k=p->adjvertex;
					        sta++;
							p=graph[k].firstarc;
						 }
						 else p=p->nextarc;
                         
						 if(!p)continue;
						 //到达公共站点e[change(h[i])][m]
						tottime+=p->time+3;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[busline1]);
					
                        //到达公共站点后
						sta=0;
						   for(p=graph[k].firstarc;p&&(k!=end);)
							if(strcmp(p->lname,t[j])==0)
							{
								tottime+=p->time;
							    k=p->adjvertex;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
							money+=judgemoney(sta,ticket[busline2]);
                        cout<<vhead<<"->"<<h[i]<<"->"<<e[change(h[i])][m]<<"->"<<t[j]<<"->"<<vtail<<"   ";
						cout<<"所用时间为："<<tottime<<"分钟,"<<"费用为："<<money<<"元"<<endl;
						count++;
					}
	return count;
}

int GRaph::oncepathtime(ElemType h[100],ElemType t[100],int counth,int countt)//看是否有转一次车路线,输出最小时间
{//其中counth为从起点出发的线路数，countt为进入终点的线路数
	//h[i]则记录了从起点出发的线路名，h[i]为第i条的名字
	//t[j]则记录了进入终点的线路名，t[j]为第j条的名字
	//有个问题是环行线路h[i]进入的站点不要包括起点
	int i,j,m,n,k,end,busline1,busline2,money=0,sta,tottime=0,count=0,money1;
	int mintime=infinity;
	ARcType *p;
	ElemType vheadtime,hitime,e1time,t1time,vtailtime;
	p=new ARcType;

	for(i=1;i<=counth;i++)
		for(j=1;j<=countt;j++)
			for(m=1;m<=en[change(h[i])];m++)//en[change(h[i])]为线路h[i]会进入的站点数
				for(n=1;n<=fn[change(t[j])];n++)//fn[change(t[j])]为线路t[j]会从之出发的站点数
					if((strcmp(e[change(h[i])][m],f[change(t[j])][n])==0)&&strcmp(h[i],t[j]))
					{
                         //看是分段计价还是单一票制，分段为true
						//公共站点不能是起点或终点
					  busline1=change(h[i]);
					  busline2=change(t[j]);

					  if(strcmp(e[change(h[i])][m],vhead)==0)continue;
                      if(strcmp(e[change(h[i])][m],vtail)==0)continue;
					 tottime=0;
		             sta=0;
					 money=0;
					//先求所用时间,和费用
                     k=LocateVertex(vhead);					
				     end=LocateVertex(vtail);
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(h[i])][m]);)
						 if(strcmp(p->lname,h[i])==0)//沿着h[i]走但是没有走到公共站点e[change(h[i])][m]
						 {
							tottime+=p->time;
							k=p->adjvertex;
					        sta++;
							p=graph[k].firstarc;
						 }
						 else p=p->nextarc;
                         
						 if(!p)continue;
						 //到达公共站点e[change(h[i])][m]
						tottime+=p->time+3;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[busline1]);
					
                        //到达公共站点后
						sta=0;
						   for(p=graph[k].firstarc;p&&(k!=end);)
							if(strcmp(p->lname,t[j])==0)
							{
								tottime+=p->time;
							    k=p->adjvertex;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
							money+=judgemoney(sta,ticket[busline2]);
							L[change(h[i])]=1;
							L[change(t[j])]=2;
							if(tottime<mintime)
							{
								mintime=tottime;
								money1=money;
								strcpy(vheadtime,vhead);
								strcpy(hitime,h[i]);
								strcpy(e1time,e[change(h[i])][m]);
								strcpy(t1time,t[j]);
								strcpy(vtailtime,vtail);

							}
							count++;
					}
						if(count)
						{
                        cout<<vheadtime<<"->"<<hitime<<"->"<<e1time<<"->"<<t1time<<"->"<<vtailtime<<"   ";
						cout<<"所用时间为："<<mintime<<"分钟，费用为："<<money1<<"元"<<endl;
						return 1;
						}
										
	return 0;
}

int GRaph::oncepathsometime(ElemType h[100],ElemType t[100],int counth,int countt)//看是否有转一次车路线,输出最小时间
{//其中counth为从起点出发的线路数，countt为进入终点的线路数
	//h[i]则记录了从起点出发的线路名，h[i]为第i条的名字
	//t[j]则记录了进入终点的线路名，t[j]为第j条的名字
	//有个问题是环行线路h[i]进入的站点不要包括起点
	int fasttime[3],index,i,j,m,n,k,end,busline1,busline2,money=0,sta,tottime=0,count=0,mintime[3],money1[3];
	ARcType *p;
	ElemType vheadtime[3],hitime[3],e1time[3],t1time[3],vtailtime[3];
	p=new ARcType;
	for(i=0;i<3;i++)
		fasttime[i]=infinity;
	for(i=1;i<=counth;i++)
		for(j=1;j<=countt;j++)
			for(m=1;m<=en[change(h[i])];m++)//en[change(h[i])]为线路h[i]会进入的站点数
				for(n=1;n<=fn[change(t[j])];n++)//fn[change(t[j])]为线路t[j]会从之出发的站点数
					if((strcmp(e[change(h[i])][m],f[change(t[j])][n])==0)&&strcmp(h[i],t[j]))
					{
                         //看是分段计价还是单一票制，分段为true
						//公共站点不能是起点或终点
					  busline1=change(h[i]);
					  busline2=change(t[j]);

					  if(strcmp(e[change(h[i])][m],vhead)==0)continue;
                      if(strcmp(e[change(h[i])][m],vtail)==0)continue;
					 tottime=0;
		             sta=0;
					 money=0;
					//先求所用时间,和费用
                     k=LocateVertex(vhead);					
				     end=LocateVertex(vtail);
						 for(p=graph[k].firstarc;p&&strcmp(graph[k].vertexname,e[change(h[i])][m]);)
						 if(strcmp(p->lname,h[i])==0)//沿着h[i]走但是没有走到公共站点e[change(h[i])][m]
						 {
							tottime+=p->time;
							k=p->adjvertex;
					        sta++;
							p=graph[k].firstarc;
						 }
						 else p=p->nextarc;
                         
						 if(!p)continue;
						 //到达公共站点e[change(h[i])][m]
						tottime+=p->time+3;
						k=p->adjvertex;
						money+=judgemoney(sta,ticket[busline1]);
					
                        //到达公共站点后
						sta=0;
						   for(p=graph[k].firstarc;p&&(k!=end);)
							if(strcmp(p->lname,t[j])==0)
							{
								tottime+=p->time;
							    k=p->adjvertex;
								p=graph[k].firstarc;
								sta++;
							}
							else p=p->nextarc;

							if(!p)continue;
							count++;
							money+=judgemoney(sta,ticket[busline2]);
                           index=num1(fasttime,tottime,count);
							if(index!=-1)
							{
								mintime[index]=tottime;
								money1[index]=money;
								strcpy(vheadtime[index],vhead);
								strcpy(hitime[index],h[i]);
								strcpy(e1time[index],e[change(h[i])][m]);
								strcpy(t1time[index],t[j]);
								strcpy(vtailtime[index],vtail);

							}
							
					}

						if(count)
						{
							if(count>3)
							{
								count=3;
                                for(i=0;i<count;i++)
								{
									cout<<vheadtime[i]<<"->"<<hitime[i]<<"->"<<e1time[i]<<"->"<<t1time[i]<<"->"<<vtailtime[i]<<"   ";
						            cout<<"所用时间为："<<mintime[i]<<"分钟,"<<"费用为："<<money1[i]<<"元"<<endl;
								}
							}
						   return 1;
						}
	return 0;
}

//第一步，求从站点a开出的所有线路名字,复制到s[i]中,但不能和hi相等
int GRaph::findpathout(ElemType s[100],ElemType a,ElemType hi)
{
	int k,count=0;//count用来计算从站点a开出的线路
	////查找名为a的顶点在数组graph中的序号
	k=LocateVertex(a);
	while(k==-1)
	{
		cout<<"1找不到改点，正确格式为（S+四位整数）：";
		cin>>a;
		k=LocateVertex(a);
	}
	ARcType *p;
	p=new ARcType;
	p=graph[k].firstarc;
	if(!p)return 0;
	if(strcmp(p->lname,hi))
	strcpy(s[++count],p->lname);
	for(;p->nextarc;p=p->nextarc)
		if(strcmp(p->lname,p->nextarc->lname))
		if(strcmp(p->nextarc->lname,hi))
			strcpy(s[++count],p->nextarc->lname);		
	return count;
}


	//接下来求转两次车的线路。先求从f( I ,U)站点发出 的线路集R ( K) ,进入站点e( J ,V) 的线
    //路集Y( O) ;
    //如果有R(k)=Y(0),则线路H ( I) , R ( K) , T( J ) 为两次换车的线路,
    //换车站点为e( I ,U) 和f( J ,V)

int GRaph::twiceandthreepath(ElemType h[100],ElemType t[100],int counth0,int countt0,int counth1,int countt1)
{//counth0为从起点发出的线路数，countt0为进入终点的线路数
	ARcType *p;
	int bef,i,j,k,n,end,linenum[4],sta,money,time,count=0;
	int v[550];
	ElemType prer[6000],posy[6000];//记录r[i]前一条路h[i];y[i]后面一条路t[i]
    int re[6000],yf[6000];//记录r[i]出自f[][j],y[i]进入e[][j]
	for(i=0;i<600;i++)
		for(j=0;j<100;j++)
			ev[i][j]=fv[i][j]=false;

	for(i=0;i<550;i++)v[i]=0;

	counth1=countt1=0;
	for(i=1;i<=counth0;i++)
		for(j=1;j<=en[change(h[i])];j++)
		if(!ev[change(h[i])][j])
		{
           ev[change(h[i])][j]=true;
			k=findpathout(r+counth1,e[change(h[i])][j],h[i]);//f[i][j]为线路i会从站点j出来,e[i][j]为线路i会进入站点j
            for(n=counth1+1;n<=counth1+k;n++)
			{
				strcpy(prer[n],h[i]);
				re[n]=j;
			}
            counth1+=k;
			if(counth1>5800)goto a;
		}
 
a: