导游图最终版.cpp

数据结构中的一个试验程序

#include <iostream>
#include<string>
using namespace std;

#define M 10000 //定义无穷大	
#define n 15 //顶点数
			
typedef struct {
	string vexs[n];		//顶点表
    int edges[n][n];	//邻接矩阵，可看作边表
	int b,e;    //图中当前的顶点数和边数
}MGraph;
int C[n][n]={{0,3,1,M,M,M,M,M,M,M,M,M,M,M,M},{3,0,M,M,M,M,M,M,M,M,M,M,M,M,M},{1,M,0,2,M,M,2,M,M,M,M,M,M,M,M},{M,M,2,0,2,M,M,M,M,M,M,M,M,M,M}
            ,{M,M,M,2,0,2,M,M,M,M,M,M,M,M,M},{M,M,M,M,2,0,M,M,M,M,M,M,M,M,M},{M,M,2,M,M,M,0,1,M,M,M,M,M,M,M},{M,M,M,M,M,M,1,0,2,M,M,M,M,M,M}
			,{M,M,M,M,M,M,M,2,0,1,M,M,M,M,M},{M,M,M,M,M,M,M,M,1,0,2,M,M,M,M},{M,M,M,M,M,M,M,M,M,2,0,1,M,M,M},{M,M,M,M,M,M,M,M,M,M,1,0,2,M,M}
			,{M,M,M,M,M,M,M,M,M,M,M,2,0,1,M},{M,M,M,M,M,M,M,M,M,M,M,M,1,0,2},{M,M,M,M,M,M,M,M,M,M,M,M,M,2,0}};
int A[n][n]={0};
int P[n][n];

void CreateMGraph(MGraph *G);
void Floyd( int A[][n],int C[][n],int P[][n]);
void path(int i,int j,MGraph *G);
int main(void)
{
	MGraph G;
	int i=0,j=0;
	CreateMGraph(&G);
	for(i=0;i<n;i++)
	{
		cout<<"编号："<<i<<"  "<<G.vexs[i]<<endl;
	}
	cout<<"请输入你所在的地址编号:";
	cin>>i;
	cout<<endl<<"输入目的地编号：";
	cin>>j;	
	cout<<endl;
	cout<<"最短路径为:";
	Floyd(A,C,P);
	cout<<G.vexs[i]<<"->";
	path(i,j,&G);
    cout<<G.vexs[j]<<endl;
	return 0;
}

void CreateMGraph(MGraph *G)
{	
	G->vexs[0]="校门";
	G->vexs[1]="主楼";
	G->vexs[2]="行政楼";
	G->vexs[3]="试验学院";
	G->vexs[4]="管理学院";
	G->vexs[5]="理学院";
	G->vexs[6]="图书馆";
	G->vexs[7]="学子超市";
	G->vexs[8]="D楼";
	G->vexs[9]="学苑楼";
	G->vexs[10]="学士楼";
	G->vexs[11]="工大派出所";
	G->vexs[12]="三公寓";
	G->vexs[13]="A楼";
	G->vexs[14]="二公寓";

}

void Floyd( int A[n][n],int C[n][n],int P[n][n])
{ 
	int i,j,k;
	for (i=0; i< n;i++)
		for (j=0;j<n;j++)
		{
			A[i][j] = C[i][j] ;
			P[i][j] = -8;
		}
		for ( k=0; k<n; k++ )
			for ( i = 0; i <n; i++ )
				for ( j = 0; j <n; j++ )
					if ( A[i][k] + A[k][j] < A[i][j] )
					{
						A[i][j] = A[i][k] + A[k][j] ;
						P[i][j] = k;
					}
}
void path(int i,int j,MGraph *G)
{
	int k;
	k=P[i][j];
	if(k!=-8)
	{
		path(i,k,G);
		cout<<G->vexs[k]<<"->";
		path(k,j,G);
	}
}