graph.cpp

图的最短路径查询

//图类的实现文件

#include "graph.h"
#include <climits>

//构造函数
graph::graph()
{
	n=0;
	edgelist=NULL;
	vexlist=NULL;
}

//析构函数，用于释放分配的内存空间
graph::~graph()
{
	int i;
	for(i=0;i<n;i++)
		delete[] edgelist[i];
	delete[] edgelist;
}

//数据读取函数，内部函数，用于从数据文件中读取路径数据存入数组中
bool graph::readdata(string filename)
{
	int i,j;
	string tname1,tname2;
	int tweight,tprice;
	ifstream datafile;
	datafile.open(filename.c_str());
	datafile>>n;

	//分配内存空间	
	vexlist=new vexnode[n];
	edgelist=new edgenode*[n];
	for(i=0;i<n;i++)
	{
		edgelist[i]=new edgenode[n];
		for(j=0;j<n;j++)
		{
			if(i==j)
			{
				edgelist[i][j].weight=-1;
				edgelist[i][j].price=-1;
			}
			else
			{
				edgelist[i][j].weight=INT_MAX;
				edgelist[i][j].price=INT_MAX;
			}
			edgelist[i][j].pin=-1;
			edgelist[i][j].win=-1;
		}
	}

	//读取地名信息
	for(i=0;i<n;i++)
		datafile>>vexlist[i].name;

	//读取路径信息－－距离，路费
	while(1)
	{
		datafile>>tname1>>tname2>>tweight>>tprice;
		datafile.ignore(1000,'\n');
		if(!datafile) break;
		for(i=0;i<n&&tname1!=vexlist[i].name;i++);
		for(j=0;j<n&&tname2!=vexlist[j].name;j++);
		edgelist[i][j].win=i;
		edgelist[i][j].pin=i;
		edgelist[i][j].weight=tweight;
		edgelist[i][j].price=tprice;
	}
	datafile.close();
	return true;
}

//路径矩阵的计算生成函数，用于计算每两个地点间的路径信息
bool graph::creatgraph(string filename)
{
	int i,j,k;
	readdata(filename);

	//计算最短路程的路径
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(j==i) continue;
			for(k=0;k<n;k++)
			{
				if(k==i||k==j) continue;
				if(edgelist[j][i].weight==INT_MAX||edgelist[i][k].weight==INT_MAX) continue;
				if(edgelist[j][k].weight>(edgelist[j][i].weight+edgelist[i][k].weight))
				{
					edgelist[j][k].weight=edgelist[j][i].weight+edgelist[i][k].weight;
					edgelist[j][k].win=i;
				}
			}
		}
	}

	//计算最少路费的路径信息
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(j==i) continue;
			for(k=0;k<n;k++)
			{
				if(k==i||k==j) continue;
				if(edgelist[j][i].price==INT_MAX||edgelist[i][k].price==INT_MAX) continue;
				if(edgelist[j][k].price>(edgelist[j][i].price+edgelist[i][k].price))
				{
					edgelist[j][k].price=edgelist[j][i].price+edgelist[i][k].price;
					edgelist[j][k].pin=i;
				}
			}
		}
	}

	return true;
}

//查询函数，用于两地间路径的输出
bool graph::search(string start,string end)
{
	int i,j,tag;
	char ch;
	outlink *p,*q,*whead,*t,*phead;

	//特殊情况判断
	if(start==end)
	{
		cout<<"一个城市，打的去吧！！"<<endl;
		ch=getch();
		return false;
	}
	for(i=0;i<n&&start!=vexlist[i].name;i++);
	if(i==n)
	{
		cout<<start<<"不存在！！"<<endl;
		ch=getch();
		return false;
	}
	for(j=0;j<n&&end!=vexlist[j].name;j++);
	if(j==n)
	{
		cout<<end<<"不存在！！"<<endl;
		ch=getch();
		return false;
	}
	if(edgelist[i][j].weight==INT_MAX)
	{
		cout<<start<<"与"<<end<<"之间无法到达"<<endl;
		ch=getch();
		return false;
	}

	//生成最短路程的路线表
	whead=new outlink;
	p=new outlink;
	whead->node=i;
	whead->link=p;
	p->node=j;
	p->link=NULL;

	do
	{
		p=whead;
		do
		{
			q=p;
			p=p->link;
			tag=0;
			if(edgelist[q->node][p->node].win!=q->node)
			{
				t=new outlink;
				t->node=edgelist[q->node][p->node].win;
				q->link=t;
				t->link=p;
				tag=1;
			}
			if(tag) break;
			
		}while(p->link!=NULL);
	}while(tag);

	//生成最少路费的路线表
	phead=new outlink;
	p=new outlink;
	phead->node=i;
	phead->link=p;
	p->node=j;
	p->link=NULL;

	do
	{
		p=phead;
		do
		{
			q=p;
			p=p->link;
			tag=0;
			if(edgelist[q->node][p->node].pin!=q->node)
			{
				t=new outlink;
				t->node=edgelist[q->node][p->node].pin;
				q->link=t;
				t->link=p;
				tag=1;
			}
			if(tag) break;
			
		}while(p->link!=NULL);
	}while(tag);

	//输出结果
	system("cls");
	cout<<"查询结果：从"<<start<<"到"<<end<<"路线为："<<endl;
	cout<<"最短路程路线为:";
	for(p=whead;p!=NULL;p=p->link)
	{
		cout<<vexlist[p->node].name;
		if(p->link!=NULL)
			cout<<"->";
	}
	cout<<endl;
	cout<<"总路程为："<<edgelist[i][j].weight<<endl;

	cout<<"最少路费路线为:";
	for(p=phead;p!=NULL;p=p->link)
	{
		cout<<vexlist[p->node].name;
		if(p->link!=NULL)
			cout<<"->";
	}
	cout<<endl;
	cout<<"总路费为："<<edgelist[i][j].price<<endl;
	ch=getch();

	//释放查询时所用的内存空间
	for(p=phead;q!=NULL;p=q)
	{
		q=p->link;
		delete p;
	}
	for(p=whead;q!=NULL;p=q)
	{
		q=p->link;
		delete p;
	}

	return true;
}