导游图

#include <stdio.h>

#define MAX_VERTEX_NUM 10
#define INFINITY 10000
#define MAX MAX_VERTEX_NUM
#define true  1
#define false 0
#define large 999

struct AlGraph{
    int vertices[MAX];
    int vexnum;
    int arcs[MAX][MAX];/*邻接矩阵*/
   };

char name[14][20]={
"行政大楼","友谊广场",
"老图书馆",
"樱  园","桂  园",
"计算机学院",
"生命科学学院","人文学院"}; /*14个景点的名称*/
 char intro[14][100]={
"行政大楼建于国立武汉大学创立之时,许多重要机构都设立在此",
"友谊广场是测绘校区的标志性广场",
"老图书馆古典的建筑风格和很丰富的古典藏书使其成为武汉大学的标志性景点",
"樱园以其樱花而闻名于世",
"桂园是武汉大学的四大园之一",
"武汉大学计算机学院位于测绘校区（信息学部）",
"武汉大学生命科学学院是全国最有名的生物学院之一",
"武汉大学人文学院是全国最出名的几大高校人文学院之一"};/*14个景点的简介*/

 void acquiry_places (struct AlGraph G)
{
   int i;
   printf(" 所有的景点号及景点名称如下所列: \n");
   for ( i=0;i<G.vexnum;i++)
       { printf( " %d,\t %s \n ",i+1,name[i]);
         if ( i%5==4 )
          {  printf(" 请按回车键以继续查看景点名称 \n");
             getchar();
          }
       
        }
    printf("请按回车键以继续\n");
    getchar();
}

  void acquiry_info ()
 {
     int i,j;
     printf("输入你想查询的景点号: \t");
     scanf( "%d",&j);
     printf("   %d,    %s   \n",j,name[j-1]);
     printf(" %s\n",intro[j-1]);
     getchar();
     printf("请按回车键以继续\n");
     getchar();
  }

void shortpath(struct AlGraph G)
{
  int cost[MAX][MAX]; /*cost[][]记录的是路径长度*/
  int dist[MAX]; /*某源点到各顶点的最短路径长度,dist[k-1]为到所查询的景点的距离，最终只须输出该值 */
  int path[MAX]; /*某源点到终点经过的顶点有序集合的数组,即要输出的内容*/
  int s[MAX]; /*最短路径的终点判定集合,为1则已经包含*/
  int i,j,n,v0,min,u,k;/*u存放最短路径的终点,k记录所要查询的景点终点*/
  int m1,m2;
  printf("\n请输入你要查询的景点起点的编号 :");
  scanf("%d",&v0);
  if( v0<=0 || v0>G.vexnum )
   { printf("\n 你的输入有错误 \n");
     exit(-1);
   }
  printf("请输入你要到的景点的代号  : ");
  scanf("%d",&k);
  if( k<=0 || k>G.vexnum )
   { printf("\n 你的输入有错误 \n");
     exit(-1);
   }
  printf(" 请按回车键以继续\n");
  getchar();
  m1=v0;
  m2=k;
  v0--;
  k--;
  for(i=0;i<G.vexnum;i++)  /*给cost[][]赋初始值*/
    {
      for(j=0;j<G.vexnum;j++)
         cost[i][j]=G.arcs[i][j];
     }
   printf(" 初始值赋值结束 \n");
   getchar();
   for(i=0;i<G.vexnum;i++)     /* 所要景点到其他景点的路径长 */
    { dist[i]=cost[v0][i];
      if(dist[i]<large&&dist[i]>0) path[i]=v0;
      s[i]=0;
     }
  printf(" 路径求解结束 \n");
  getchar();
  clrscr();
  s[v0]=1;          /* 记录起始点 */     
  for(i=0;i<G.vexnum;i++)
    { min=large;
      u=v0;
      for(j=0;j<G.vexnum;j++)
        if(s[j]==0&&dist[j]<min)
          {min=dist[j];u=j;}
      s[u]=1;   /*u顶点是求得最短路径的顶点编号,置1表示记录下*/
      for(j=0;j<G.vexnum;j++)
         if(s[j]==0&&dist[u]+cost[u][j]<dist[j])
           { dist[j]=dist[u]+cost[u][j];
             path[j]=u;
            }
      }
  printf("输出 % s 到各个景点的距离  \n" ,name[m1-1]);
  for(i=0;i<G.vexnum;i++)
    if(i!=m1-1)
      printf("  %d米  \t   %s \n",dist[i],name[i]);
 getchar();   
printf("\n 顶点 %s 到 %s 的最短路径长度为和途径如下 :\n",name[m1-1],name[m2-1]);

  getchar();
  i=m1;/*输出结果*/
     printf("%s\t",name[u]);
     if(s[i]==1)
       { u=i;
         while(u!=v0)
            { getchar();
              printf("中间途经---%s  ",name[u]);
              u=path[u];
             }
          printf("\n  路径长度是%d米  ",dist[i]);
          printf(" \n 输出结束 \n");
          getchar();
         }
     
}

  main()
{ int i,j;
  struct AlGraph G;
  G.vexnum=8;
  clrscr();
  /* 初始化邻接矩阵 */
  for(i=0;i<G.vexnum;i++)
   for(j=0;j<G.vexnum;j++)
      G.arcs[i][j]=INFINITY;
  for(i=0;i<G.vexnum;i++)
    G.arcs[i][i]=0;
   /* 有直通路径的赋值 */
  G.arcs[0][1]=200;   G.arcs[0][2]=100;    G.arcs[0][3]=400;    G.arcs[0][4]=200;    
  G.arcs[1][0]=200;   G.arcs[1][2]=100;    G.arcs[1][5]=400;    G.arcs[1][6]=200;
  G.arcs[2][0]=100;   G.arcs[2][1]=100;    G.arcs[2][3]=200;   
  G.arcs[3][0]=400;   G.arcs[3][2]=200;    G.arcs[3][4]=200;    G.arcs[3][6]=300;    G.arcs[3][7]=400;
  G.arcs[4][0]=200;   G.arcs[4][3]=200;      
  G.arcs[5][1]=400;   G.arcs[5][6]=200; 
  G.arcs[6][1]=200;   G.arcs[6][3]=300;    G.arcs[6][5]=200;    G.arcs[6][7]=100;  
  G.arcs[7][3]=400;   G.arcs[7][6]=100;   
 
  printf(" 景点的数目是 : %d \n",G.vexnum);
  getchar();
 loop: clrscr();
       printf("               武汉大学景点查询                \n");
       printf("*********************************************************\n");
       printf(" 1.输出所有的景点            \n");
       printf(" 2.输出你所选择的景点相关信息:\n");
       printf(" 3.获取所选景点间的最短路径: \n");
       printf(" 4.退出                                                \n");
       printf("*********************************************************\n");
       printf(" 请选择: \t");
 
  
  scanf(" %d",&i );
  switch(i)
    {   case 1 : acquiry_places(G);break;
        case 2 : acquiry_info();break;
        case 3 : shortpath (G) ;break;
        case 4 : exit(0);
        default: printf(" 错误的输入:\n");
    }
 
  goto loop;
}