最短路径.cpp

设计一个校园导游程序

#include"图.h"
#include<stdio.h>

#define INFINITY  300

typedef struct{
  int vx,vy;
}Edge;

typedef struct{
  Edge edges[MAXVTXNUM];
  int len;
}PathType,Parray[MAXVTXNUM][MAXVTXNUM];

typedef struct{
  char vertices[MAXVTXNUM][30];
  int num;
}PType;

typedef struct{
  int a;
}Int,array[MAXVTXNUM][MAXVTXNUM];

Parray P;
array D;
PType ALLP[MAXVTXNUM][MAXVTXNUM];

void InitPath(PathType&pa)
{
  pa.len=0;
}//Initpath

void OutPath(Graph g,PathType pa,PType&vtxes)
{
  int m=0;
  VertexType vtx;
  for(int i=0;i<pa.len;i++)
  {
    GetVex(g,pa.edges[i].vx,vtx);
	strcpy(vtxes.vertices[m++],vtx.name);
  }
  GetVex(g,pa.edges[pa.len].vy,vtx);
  strcpy(vtxes.vertices[m],vtx.name);
  vtxes.num=m;
}//OutPath 存在问题

void ShortestPath(Graph g,Parray P,array D)
{
  EdgePtr e=NULL;
  int u,v,w,i,j;
  for( v=0;v<g.vexNum;++v)
    for( w=0;w<g.vexNum;++w)
	{
	  D[v][w].a=INFINITY;
	  for(EdgePtr e=FirstEdge(g,v);e;NextEdge(g,v,e,e))
		  if(v==w)D[v][w].a=0;
		  else if((e->elem.ivex==v&&e->elem.jvex==w)||(e->elem.ivex==w&&e->elem.jvex==v))
			  D[v][w].a=e->elem.length;
	  for( u=0;u<g.vexNum;++u)
		  if(D[v][w].a<INFINITY)
		  {
		    P[v][w].edges[P[v][w].len].vx=v;
			P[v][w].edges[P[v][w].len].vy=w;
			P[v][w].len=1;
		  }//if
	}//for
  for(u=0;u<g.vexNum;++u)
	  for(v=0;v<g.vexNum;++v)
		  for(w=0;w<g.vexNum;++w)
			  if(D[v][u].a+D[u][w].a<D[v][w].a)
			  {
				  D[v][w].a=D[v][u].a+D[u][w].a;
				  for( i=0;i<P[v][u].len;++i)
				      P[v][w].edges[i]=P[v][u].edges[i];
				  for( j=0;j<P[u][w].len;++j)
					  P[v][w].edges[i+j]=P[u][w].edges[j];
				  P[v][w].len=P[v][u].len+P[u][w].len;
			  }//if
}//ShortestPath 

void OutSP(Graph g)
{
  int m,n,i;
  char a;
  do{
      cout<<"\n请输入开始的景点序号：";
      cin>>m;
      cout<<"\n请输入最终的景点序号：";
	  cin>>n;
      for(i=0;i<=ALLP[m][n].num;i++)
	  {
	      if(i==0) cout<<"（起点）"<<g.Adjmulist[m].data.name<<"——";
	      else if(i==ALLP[m][n].num) cout<<g.Adjmulist[n].data.name<<"（终点）";
	      else cout<<ALLP[m][n].vertices[i]<<"——";
	  }
      cout<<endl<<"路径长度为："<<D[m][n].a<<endl ;
	  cout<<"请选择：结束查询——q		继续查询——c：";
	  cin>>a;
  }while(a!='q');
}//OutSP


void main()
{
  char ch;
  char str[100];
  int c,i,j,m=0,n=0;
  cout<<"\n				校园导游咨询 \n";
  Graph g;
  InitGraph(g);
  cout<<"\n请输入校园景点数据的源文件路径：\n(例：e:\\校园景点路径.txt)：";
  cin>>str;
  CreateGraph(g,str);
  ShowGraph(g);
  for( i=0;i<MAXVTXNUM;i++)
	     for(j=0;j<MAXVTXNUM;j++)
		       InitPath(P[i][j]);
  ShortestPath(g,P,D);
  for( i=0;i<MAXVTXNUM;i++)
	     for( j=0;j<MAXVTXNUM;j++)
		       OutPath(g,P[i][j],ALLP[i][j]);
  do{
     cout<<"\n请选择：\nc——重建路径\nv——显示景点信息\np——查询最短路径\nq——退出系统\n你的选择为：";
     cin>>ch;
     switch(ch)
	 {
	 case 'c':  InitGraph(g);
                 cout<<"\n请输入校园景点数据的源文件路径：\n(例：e:\\校园景点路径.txt)：";
				cin>>str;
				if(CreateGraph(g,str))
				  ShowGraph(g);
				break;
	 case 'v':  cout<<"\n请输入景点的编号：";
		        cin>>c;
				ShowVex(g,c);
				break;
	 case 'p':  OutSP(g);
                break;
	 default:   cout<<"对不起，你的选择有错误！";
	 }
  }while(ch!='q'&&ch!='Q');
}