goto.cpp

GSP寻找最短路径的算法 可以用文件保存输入的信息 存储地址D：//存储.txt

#include <iostream.h>
#include "AdjacencyWDigraph.h"//加权有向邻接矩阵
#include <string>
void main()
{
	char ans;
	do{
		system("cls");
		cout<<"=======================GPS寻找最短路径==========================="<<endl<<endl;
		cout<<"------------你是一名游客 你想尽快到达想去的地点------------------"<<endl;
		cout<<"--------------先输入标志物的数目及相互联通情况-------------------"<<endl;
		cout<<"----------------记各个标志物为代号1-10等数字---------------------"<<endl;
		cout<<"--------------输入游客现在的位置以及他的目的地-------------------"<<endl;
		cout<<"----------------程序给出最短路径 指引游客前行--------------------"<<endl<<endl;
		cout<<"使用请按'E'  退出请按'Q'."<<endl;
		cin>>ans;
	}while(ans!='E'&&ans!='e'&&ans!='Q'&&ans!='q');
	while(ans=='E'||ans=='e')
	{
	system("cls");
	cout<<"  使用以往道路情况表 请按'I' "<<endl<<endl;
	cout<<"  重新制作道路情况表 请按'K' "<<endl<<endl;
	AdjacencyWDigraph<int> G(10,0);
	cin>>ans;
	int c,a1,a2,a3;
	if(ans=='I'||ans=='i')
	{
		system("cls");
		G.initial();
		G.Outpput();
	}
	else if(ans=='K'||ans=='k')
	{
		system("cls");
		cout<<"请输入标志物的数目"<<endl;
		cin>>c;
		G.initial(c);
	}
	else
		return;
//	G.Add(1,2,4).Add(2,5,5).Add(1,3,2).Add(3,4,1).Add(4,5,3).Add(1,5,8).Add(2,4,4);
	cout<<"添加连通情况 请按'A' 删除请按'D' "<<endl;		
	cin>>ans;
	if(ans=='A'||ans=='a')
	{
		cout<<"格式如：(1,3,4)表示1 到3 需要4 个单位时间 结束时请输入'0 0 0'  "<<endl;
		while(true)
		{
			cin>>a1>>a2>>a3;
			if(a1==0)
				break;
			G.Add(a1,a2,a3);
		}
	}
	else if(ans=='D'||ans=='d')
	{
		cout<<"格式如：(1,3)表示删除1 到3 的连通 结束时请输入'0 0'  "<<endl;
		while(true)
		{
			cin>>a1>>a2;
			if(a1==0)
				break;
			G.Delete(a1,a2);
		}
	}
	system("cls");
	cout<<"现在顶点数为："<<G.Vertices()<<"  边数为："<<G.Edges()<<endl;
	G.Outpput();
	cout<<"是否储存本次输入情况 储存请按'Y' "<<endl;
	cin>>ans;
	if(ans=='Y'||ans=='y')
		G.keep();
	system("cls");
	G.Outpput();
	int i,j,m=0;
	cout<<"输入起点"<<endl;
	cin>>i;
	cout<<"输入终点"<<endl;
	cin>>j;
	c=j;
	if(i==j)
	{
		cout<<"正是您此刻所在的位置！"<<endl;
		break;
	}
	int d[6];//长度
	int p[6];//前继节点
	int path[6];//存储路径
	G.ShortestPaths(i,d,p);
	if(!p[j])
	{
		 cout<<"对不起 没有可以通行的路！"<<endl;
		 break;
	}
	cout<<"最短路径为"<<endl;
     while(p[j]!=0)
	 {   
		 path[m]=p[j];
         j=p[j];
		 if(j==i)//当走到前继节点为0或s时结束 以免出现无穷循环
			 break;
		 m++;
	 }
	 for(int f=m;f>=0;f--)
		cout<<path[f]<<" ";
   	cout<<c<<endl;
	cout<<"路径长度为："<<d[c]<<endl<<endl;
	cout<<"使用请按'E',退出请按'Q'."<<endl;
	cin>>ans;
	}
	cout<<"程序结束 任意键离开界面........"<<endl;
	cin>>ans;
}