traffic.cpp

全国交通算法,求最短路径,最省时间,最少工作量. VC开发的,很有借鉴意义

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Graph.h"
#include "Time.h"
#include "Path.h"

#define NULL 0

bool OpenGraph_T(Graph &G);
bool OpenGraph_P(Graph &G);
int  Main_Menu(Graph &GT,Graph &GP);
bool SaveGraph_T(Graph G); 
bool SaveGraph_P(Graph G);

void main()
{
	Graph GT;      //火车交通图
	Graph GP;      //飞机交通图  
	
	CreateGraph(GT); //建立空的火车交通图
	CreateGraph(GP); //建立空的飞机交通图

	OpenGraph_T(GT);  //打开已经存在火车的数据
	OpenGraph_P(GP);  //打开已经存在飞机的数据

	Main_Menu(GT,GP); 

	SaveGraph_T(GT);     //保存火车数据
	SaveGraph_P(GP);     //保存飞机数据

	DestoryGraph(GT);
	DestoryGraph(GP);

}

/******************< 迪杰斯特拉算法 求取最少钱数和最短时间 >********************/

void LeastMoneyPath(Graph G, int st, int nd, Path &pathA)     
	//st：起点号，nd：终点号，结果存储在pathA中  
	//path包括路径的长度，起点，终点和路径信息
{
	//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
	//最短路径PathInfo,路径长度pathLength
	//设int dijkst[MAXVTXNUM];Path path[MAXVTXNUM];
	int i;
	int dijkst[MAXVTXNUM];
	bool final[MAXVTXNUM]={false}; 
	Path path[MAXVTXNUM];  //每个顶点都有路径  
	EdgeNode *p,*q;        //边的信息     弧结点     
	EdgeInfo t;          //边的信息
	bool found;
	int min=9999,min_i,v,w;
	for(i=0;i<MAXVTXNUM;i++)             //初始化
	{
		dijkst[i]=9999;
		InitPath(path[i]);    //path[i].len=0;
	}
	p=G.Adjlist[st].firstEdge;
	while(p)                            //初始化dijkst数组，检测依附于起始点的每一条边
	{
		q=p->nextEdge;
		if(p->elem.Money<dijkst[p->elem.jvex])
		{
			dijkst[p->elem.jvex]=p->elem.Money;
			t=p->elem;
			SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
		}
		p=q;		
	}
	found= false;
	while(!found)
	{
		//在所有未求得最短路径的顶点求使得dijkst[i]取最小的i
		for(i=0;i<MAXVTXNUM;i++)
		{
			if(final[i]==false && dijkst[i]<min)
				min_i=i;
		}

		final[min_i]=true;

		if(min_i==nd) 
			found=true;
		else
		{
			v=min_i;
			p=G.Adjlist[v].firstEdge;
			while(p)
			{
				q=p->nextEdge;
				w=p->elem.jvex;
				if(final[w]==false &&((dijkst[v]+p->elem.Money)<dijkst[w]))
				{
					dijkst[w]=dijkst[v]+p->elem.Money;
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w,p->elem);
				}
				p=q;
			} //while(p)
		} //else
	}// while(!found)

	copyPath(pathA,path[nd]);
}


void ShortestTimePath(Graph G, int st, int nd, int n ,Path &pathA)
{
	//st：起点号，nd：终点号，n：当前时间（秒），结果存储在pathA中
	
	//利用迪杰斯特拉算法的基本思想求图G中从顶点st到nd的一条
	//最短路径PathInfo,路径长度pathLength
	//设int dijkst[MAXVTXNUM];Path path[MAXVTXNUM];
	int i;
	int dijkst[MAXVTXNUM];
	bool final[MAXVTXNUM]={false}; 
	int now[MAXVTXNUM];
	Path path[MAXVTXNUM];
	EdgeNode *p,*q;
	EdgeInfo t;
	bool found;
	int min=99999,min_i,v,w,time;
	for(i=0;i<MAXVTXNUM;i++)             //初始化
	{
		dijkst[i]=99999;
		InitPath(path[i]);
		now[i]=0;
	}
	now[st]=n;

	p=G.Adjlist[st].firstEdge;
	while(p)                            //初始化dijkst数组，检测依附于起始点的每一条边
	{
		q=p->nextEdge;
		if(p->elem.StartTime<now[st]&&p->elem.EndTime>=now[st])
		{
			time= 1440-TimeSub(p->elem.EndTime,now[st]);
		}
		else
			time= TimeSub(p->elem.EndTime,now[st]);
			

		if(time<dijkst[p->elem.jvex])
		{
			dijkst[p->elem.jvex]=time;
			t=p->elem;
			SetPath(path[p->elem.jvex],st,p->elem.jvex,t);
			now[p->elem.jvex]=p->elem.EndTime;
		}
		p=q;		
	}
	found= false;
	while(!found)
	{
		//在所有未求得最短路径的顶点求使得dijkst[i]取最小的i
		for(i=0;i<MAXVTXNUM;i++)
		{
			if(final[i]==false && dijkst[i]<min)
				min_i=i;
		}

		final[min_i]=true;

		if(min_i==nd) 
			found=true;
		else
		{
			v=min_i;
			p=G.Adjlist[v].firstEdge;
			while(p)
			{
				q=p->nextEdge;
				w=p->elem.jvex;

				if(final[w]==false &&(dijkst[v]+TimeSub(p->elem.EndTime,now[v])<dijkst[w]))
				{
					dijkst[w]=dijkst[v]+TimeSub(p->elem.EndTime,now[v]);
					copyPath(path[w],path[v]);
					InsertPath(path[w],v,w,p->elem);
				}
				p=q;
			} //while(p)
		} //else
	}// while(!found)
	copyPath(pathA,path[nd]);
}


bool OpenGraph_T(Graph &G)          //打开火车交通图
{
	FILE *fp;
	char c='\n';
	int i=0,j=0;
	if((fp = fopen("Train.txt","r")) == NULL)
	{
		return false;
	}
   fscanf(fp,"%d",&G.vexNum); //图的顶点数    //按指定格式从文件中读出数据
   fscanf(fp,"%d",&G.edgeNum); //图的边数

	while(j<G.vexNum) 
	{
		 fscanf(fp,"%d,%d,%s",&G.Adjlist[i].cityNumber,&G.Flag[i],&G.Adjlist[i].cityName);
		 G.Adjlist[i].firstEdge = NULL;
		 if(G.Flag[i]==1)
			 j++;
		 i++;
	 }

	 for(i = 0;i<G.edgeNum;i++)
	 {
		 EdgeNode *p = new EdgeNode ;
		 
		 fscanf(fp,"%d,%d",&p->elem.ivex,&p->elem.jvex);
		 fscanf(fp,"%d,%d,%d,%d",&p->elem.Money,&p->elem.StartTime,&p->elem.EndTime,&p->elem.Time);
		 fscanf(fp,"%s",&p->elem.Number);

		 p->nextEdge=G.Adjlist[p->elem.ivex].firstEdge;
		 G.Adjlist[p->elem.ivex].firstEdge=p;
	 }
	 fclose(fp);
	 return true;
}

bool OpenGraph_P(Graph &G)     //打开飞机交通图
{
	FILE *fp;
	char c='\n';
	int i=0,j=0;
	if((fp = fopen("Plane.txt","r")) == NULL)  //打开一个文件  r/w 只　读/写　方式打开一个文本文件
	{                                           //返回文件指针，打开失败返回NULL
		return false;
	}
   fscanf(fp,"%d",&G.vexNum);    //按指定格式从文件中读出数据
   fscanf(fp,"%d",&G.edgeNum);

	while(j<G.vexNum) 
	{
		 fscanf(fp,"%d,%d,%s",&G.Adjlist[i].cityNumber,&G.Flag[i],&G.Adjlist[i].cityName);
		 G.Adjlist[i].firstEdge = NULL;
		 if(G.Flag[i]==1)
			 j++;
		 i++;
	 }

	 for(i = 0;i<G.edgeNum;i++)
	 {
		 EdgeNode *p = new EdgeNode ;
		 
		 fscanf(fp,"%d,%d",&p->elem.ivex,&p->elem.jvex);
		 fscanf(fp,"%d,%d,%d,%d",&p->elem.Money,&p->elem.StartTime,&p->elem.EndTime,&p->elem.Time);
		 fscanf(fp,"%s",&p->elem.Number);

		 p->nextEdge=G.Adjlist[p->elem.ivex].firstEdge;
		 G.Adjlist[p->elem.ivex].firstEdge=p;
	 }
	 fclose(fp);
	 return true;
}

bool SaveGraph_T(Graph G)    //保存火车图信息
{
	FILE *fp;
	int i,j=0;
	char c = '\n';
	EdgeNode *p;
	
	if((fp = fopen("Train.txt","w")) == NULL)
	{
		cout << ("不能建立文件：Train.txt");
		return false;
	}
	fprintf(fp,"%d\n",G.vexNum);//将格式化数据写入流式文件中
    fprintf(fp,"%d\n",G.edgeNum);
	j=0;
	i=0;
	while(j<G.vexNum)
	{
		fprintf(fp,"%d,%d,%s%c",i,G.Flag[i],G.Adjlist[i].cityName,c);
		if(G.Flag[i]==1)
			j++;
		i++;
	}
	i=0;
	j=0;
	while(j<G.vexNum)
	{
		p = G.Adjlist[i].firstEdge;
		while(p !=NULL)
		{
				fprintf(fp,"%d,%d\n",i,p->elem.jvex);
				fprintf(fp,"%d,%d,%d,%d\n",p->elem.Money,p->elem.StartTime,p->elem.EndTime,p->elem.Time);
				fprintf(fp,"%s%c",p->elem.Number,c);
			p = p->nextEdge;
		}
		if(G.Flag[i]==1)
			j++;
		i++;

	}
	fclose(fp);
	return true;
	
}


bool SaveGraph_P(Graph G)         //保存飞机图信息
{
	FILE *fp;
	int i,j=0;
	char c = '\n';
	EdgeNode *p;
	
	if((fp = fopen("Plane.txt","w")) == NULL)
	{
		cout << "不能建立文件：Plane.txt" << endl;
		return false;
	}
	fprintf(fp,"%d\n",G.vexNum);
    fprintf(fp,"%d\n",G.edgeNum);
	j=0;
	i=0;
	while(j<G.vexNum)
	{
		fprintf(fp,"%d,%d,%s%c",i,G.Flag[i],G.Adjlist[i].cityName,c);
		if(G.Flag[i]==1)
			j++;
		i++;
	}
	i=0;
	j=0;
	while(j<G.vexNum)
	{
		p = G.Adjlist[i].firstEdge;
		while(p !=NULL)
		{
				fprintf(fp,"%d,%d\n",i,p->elem.jvex);
				fprintf(fp,"%d,%d,%d,%d\n",p->elem.Money,p->elem.StartTime,p->elem.EndTime,p->elem.Time);
				fprintf(fp,"%s%c",p->elem.Number,c);
			p = p->nextEdge;
		}
		if(G.Flag[i]==1)
			j++;
		i++;

	}
	fclose(fp);
	return true;
	
}

bool input_Vex(Graph G,int &i)
{
	char name[10];
	cin >> name;
	
	fflush(stdin);  //清除文件缓冲区，文件以写方式打开时将缓冲区内容写入文件
	if(LocateVex(G,name,i)==true)
		return true;
	else
	{
		cout << "该城市不存在！\n";
		return false;
	}
}

bool input_Number(Graph G, int st,int sn,char *number)
{
	cin >> number;
	if(LocateEdge(G,st,sn,number)==true)
		return true;
	else
	{
		cout << "该路线不存在！\n";
		return false;
	}
}


void input_Money(Graph G, int &st,int &sn)
{
	while(1)
	{
		cout << "请输入起始城市名称：" ;
		if(input_Vex(G,st)==true)
			break;
	}
	while(1)
	{
		cout << "请输入到达城市名称：" ;
		if(input_Vex(G,sn)==true)
			break;
	}
}
	
void input_Time(Graph G, int &st,int &sn,int &time)
{
	int hour,minute;
	while(1)
	{
		cout << "请输入起始城市名称：" ;
		if(input_Vex(G,st)==true)
			break;
	}
	while(1)
	{
		cout << "请输入到达城市名称：" ;
		if(input_Vex(G,sn)==true)
			break;
	}
	cout << "请输入拟出发时间： "<<"\n";
	cout << "  几点:";
	cin >> hour;
	cout << "几分: ";
	cin >> minute;
	time=TimeChange(hour,minute);
}


void print_Money(Graph GT, Path p)             //最少钱输出
{
	int i;
	int sum=0;
	cout << "最省钱路线:" << endl << endl;
	for(i=0;i<p.len;i++)
	{
		cout << "No:   " << i+1;
		cout << p.edges[i].p.Number ;
		cout << "\n\t\t";
		cout << "始发: ";
		cout << "\t" << p.edges[i].p.ivex <<"  " << GT.Adjlist[p.edges[i].p.ivex].cityName;
		PrintTime(p.edges[i].p.StartTime);	
		cout << "\n\t\t";
		cout << "到达:";
		cout << "\t" << p.edges[i].p.jvex <<"  "  << GT.Adjlist[p.edges[i].p.jvex].cityName;
		PrintTime(p.edges[i].p.EndTime);
		cout <<"票价: " <<  p.edges[i].p.Money << "元";
		sum+=p.edges[i].p.Money;
		cout << "\n\n";
	}
	cout << "总共费用："<< sum << " 元 " << "\n\n";

}

void print_Time(Graph GT, Path p, int now)    //now是用户自定义的查询时间,和求取时候的参数now一致
{	
	int i,sum_Time=0,hour=0,minute=0;
	cout << "\n最快到达路线:\n\n";
	for(i=0;i<p.len;i++)                   //最短时间输出
	{
		cout << "No:  " << i+1;
		cout << "    "<< p.edges[i].p.Number;