图.cpp

以上一共五个在VC环境下编写的程序

#include <iostream.h>
#include <stdlib.h>

#define Maxvex 20    //最大结点数
#define FALUSE 0     //没找到最短路径
#define TURE 1       //找到最短路径

int IN=32767;        //没有路径INFINITY
int vexnum;          //结点数

int P[Maxvex][Maxvex][Maxvex];    //保存所有路径
int D[Maxvex][Maxvex];    //保存权值


int arcs[9][9]={0,    2,    32767,32767,32767,4,    32767,5,    32767,
				2,    0,    2,    32767,32767,3,    32767,4,    32767,
				32767,2,    0,    2,    32767,3,    32767,5,    32767,
				32767,32767,2,    0,    3,    32767,32767,32767,6,
			    32767,32767,32767,3,    0,    32767,4,    32767,32767,
				4,    3,    3,    32767,32767,0,    4,    32767,32767,
				32767,32767,32767,32767,4,    4,    0,    32767,32767,
				5,    4,    5,    32767,32767,32767,32767,0,    32767,
			    32767,32767,32767,6,    32767,32767,32767,32767,0     };  //图的邻接矩阵

void InitMGraph()//初始化图函数！
{
	vexnum=9;
}

void PrintIn()//打印信息函数！
{
	char chioce;
loop1:cout<<"请输入要查找的景点(A----I)(Q,q退出): "<<endl;
	  cin>>chioce;
	  switch(chioce)
	  {
	  case'A':cout<<"东北大学正北门。----有1993年改名的东北大学校牌和研究院校牌。"<<endl;goto loop1;
	  case'B':cout<<"教学主楼。----是同学进行信息类实验,以及信息学院老师的办公室和实验室。"<<endl;goto loop1;
	  case'C':cout<<"宁恩成图书馆。----藏书百万。"<<endl;goto loop1;
	  case'D':cout<<"春华园。----风景如画。"<<endl;goto loop1;
	  case'E':cout<<"秋实林。----芬芳四溢。"<<endl;goto loop1;
	  case'F':cout<<"计算中心。----东北地区网络中心。"<<endl;goto loop1;
	  case'G':cout<<"汉卿会堂。----重要会议，招聘会和宣讲会的地方。"<<endl;goto loop1;
	  case'H':cout<<"科学馆。----位于三好街商业区。"<<endl;goto loop1;
	  case'I':cout<<"东北大学南门。----公共汽车244终点站。"<<endl;goto loop1;
	  case'Q':
	  case'q':break;
	  default:cout<<"没有这个景点！"<<endl;goto loop1;
	  }
}

int LocateVex(char T)
{
	switch(T)
	{
	case'A':return 0;break;
	case'B':return 1;break;
	case'C':return 2;break;
	case'D':return 3;break;
	case'E':return 4;break;
	case'F':return 5;break;
	case'G':return 6;break;
	case'H':return 7;break;
	case'I':return 8;break;
	default:cout<<"输入错误！"<<endl;
	}
}

void ShortestTowPath(char b,char e)//判断两个最小路径的主要算法！
{
	int i;
	int v,w,vv,ww;
	int u;
	vv=LocateVex(b);
	ww=LocateVex(e);

	for(v=0;v<vexnum;++v)
	{
		for(w=0;w<vexnum;++w)
		{
			D[v][w]=arcs[v][w];
			for(u=0;u<vexnum;++u)
				P[v][w][u]=FALUSE;
			if(D[v][w]<IN)
			{
				P[v][w][v]=TURE;
				P[v][w][w]=TURE;
			}//if
		}//for
	}
    for(u=0;u<vexnum;++u)
	{
		for(v=0;v<vexnum;++v)
		{
			for(w=0;w<vexnum;++w)
			{
				if(D[v][u]+D[u][w]<D[v][w])
				{
					D[v][w]=D[v][u]+D[u][w];
					for(i=0;i<vexnum;++i)
					{
						P[v][w][i]=P[v][u][i]||P[u][w][i];
					}   //for
				}   //if
			}   //for
		}
	} 
	cout<<"最短路径为："<<endl;
	for(i=0;i<vexnum;i++)
	{
		if(P[vv][ww][i]==TURE)
		{
			switch(i)
			{
			case 0:cout<<" "<<"A";break;
			case 1:cout<<" "<<"B";break;
			case 2:cout<<" "<<"C";break;
			case 3:cout<<" "<<"D";break;
			case 4:cout<<" "<<"E";break;
			case 5:cout<<" "<<"F";break;
			case 6:cout<<" "<<"G";break;
			case 7:cout<<" "<<"H";break;
			case 8:cout<<" "<<"I";break;
			default:cout<<"程序出错！"<<endl;
			}
		}
		else continue;
	}
	cout<<endl;
	cout<<"路径长度为：";
	cout<<D[vv][ww]<<endl;
}

void SearchPath()//查找最短路径
{
	int temp;
	char start,end;
	do{
		cout<<"请输入启始景点代码（A----I）："<<endl;
		cin>>start;
		if('A'>start||start>'I')
		{
			cout<<"没有这个景点！"<<endl;
			temp=0;
		}
		else temp=1;
	}while(temp==0);
	do{
		cout<<"请输入终止景点代码（A----I）："<<endl;
		cin>>end;
		if('A'>end||end>'I')
		{
			cout<<"没有这个景点！"<<endl;
			temp=0;
		}
		if(end==start)
		{
			cout<<"景点重复！"<<endl;
			temp=0;
		}
		else temp=1;
	}while(temp==0);
	ShortestTowPath(start,end);
}

void main()
{
	int a;

	cout<<"          *************** 东北大学校园导游系统 *************** "<<endl;
	cout<<endl;
	cout<<"                     ****  东北大学校园平面图  ****          "<<endl;
	cout<<endl;
	cout<<"                                   (A)               "<<endl;
	cout<<"                                   ***               "<<endl;
	cout<<"                                  * *  *             "<<endl;
	cout<<"                                4*  *2   *5          "<<endl;
	cout<<"                                *   *      *         "<<endl;
	cout<<"                             (F)*3*(B)**4**(H)       "<<endl;
	cout<<"                              * *   *      *         "<<endl;
	cout<<"                            4*   *3 *2   *5          "<<endl;
	cout<<"                            *     * *  *             "<<endl;
	cout<<"                          (G)      (C)               "<<endl;
	cout<<"                            *       *                "<<endl;
	cout<<"                            4*      *2               "<<endl;
	cout<<"                            (E)**3**(D)              "<<endl;
	cout<<"                                    *                "<<endl;
	cout<<"                                    *                "<<endl;
	cout<<"                                    *6               "<<endl;
	cout<<"                                    *                "<<endl;
	cout<<"                                    *                "<<endl;
	cout<<"                                   (I)               "<<endl;
	cout<<endl;
    InitMGraph();   //出事初始化图函数
	cout<<"                       --------功能菜单:--------"<<endl;
	cout<<"                          1:显示指定景点信息;"<<endl;
	cout<<"                          2:查找最短路径;"<<endl;
	cout<<"                          3:退出。"<<endl;
	cout<<"                       -------------------------"<<endl;
loop:cout<<"                      >>>>>>>>请选择功能：";
	 cin>>a;
	 if(a==1)
	 {
		 PrintIn();
		 goto loop;
	 }
	 if(a==2)
	 {
		 SearchPath();
		 goto loop;
	 }
	 if(a==3) exit(0);
	 else {
		 cout<<"没有这个功能！"<<endl;
		 goto loop;
	 }
}//main