dijkstra.txt

校园导游咨询 C++程序 用于查询校园景点最短路径

//暂时还不会求所有路径的程序
#include<stdio.h> 
#include<stdlib.h>

#define INT_MAX 20000
#define NUM 10

long int D[NUM];   /* 辅助变量存储最短路径长度 */
int p[NUM];

typedef struct 
{
	int adj;
}ArcCell;

typedef struct 
{
	int number;
	char *name;
	char *imformation;
}Arctex;

typedef struct 
{
  Arctex arcvex[10];
  ArcCell arcs[10][10];
}Graph;

void initGraph(Graph &G)
{
	for(int i=0;i<=10;i++)
		for(int j=0;j<=10;j++)
			G.arcs[i][j].adj=INT_MAX;
}

void Creatgraph(Graph &G)
{
	for(int i=0;i<=10;i++)
		G.arcvex[i].number=i;
	G.arcvex[0].name="学校南大门";
    G.arcvex[0].imformation="建筑宏伟，长一百多米，为各大院校之首";
	G.arcvex[1].name="第一教学楼";
    G.arcvex[1].imformation="我校第一学院->计算机学院就位列其中，绝对是人才的集中地";
	G.arcvex[2].name="行政楼";
    G.arcvex[2].imformation="我校高级领导全数在内，就连财务处也身居其中，可谓我校精华所在";
	G.arcvex[3].name="第三教研楼";
    G.arcvex[3].imformation="同学上机学习的地方，内有百台计算机，是培育人才的摇篮";
	G.arcvex[4].name="篮球场";
    G.arcvex[4].imformation="同学们最喜欢的体育锻炼场所";
	G.arcvex[5].name="田径场";
    G.arcvex[5].imformation="跑道、篮球场、足球场，单干……应有尽有";
	G.arcvex[6].name="文化活动中心";
    G.arcvex[6].imformation="一个让同学们忘记愁累的地方，是不可缺少的娱乐休闲中心";
	G.arcvex[7].name="体育馆";
    G.arcvex[7].imformation="想看浙江万马VS浙江广厦的德比篮球赛吗，那就来吧！";
	G.arcvex[8].name="综合楼";
    G.arcvex[8].imformation="如果你生病了怎么办？综合楼为你提供最舒适的服务，让你立刻好起来";
	G.arcvex[9].name="图书馆";
    G.arcvex[9].imformation="它是知识的殿堂，它是学术的领地，它是同学们最最喜欢的";
     
    G.arcs[0][1].adj=G.arcs[1][0].adj=40;
    G.arcs[0][2].adj=G.arcs[2][0].adj=50;
    G.arcs[1][2].adj=G.arcs[2][1].adj=50;
    G.arcs[1][3].adj=G.arcs[3][1].adj=20;
    G.arcs[2][4].adj=G.arcs[4][2].adj=60;
    G.arcs[3][4].adj=G.arcs[4][3].adj=180;
    G.arcs[3][5].adj=G.arcs[5][3].adj=150;
    G.arcs[3][6].adj=G.arcs[6][3].adj=100;
    G.arcs[3][9].adj=G.arcs[9][3].adj=20;
    G.arcs[4][7].adj=G.arcs[7][4].adj=20;
    G.arcs[5][6].adj=G.arcs[6][5].adj=30;
    G.arcs[6][8].adj=G.arcs[8][6].adj=30;
    G.arcs[6][9].adj=G.arcs[9][6].adj=40;
    G.arcs[7][9].adj=G.arcs[9][7].adj=40;
    G.arcs[8][9].adj=G.arcs[9][8].adj=30;
}

void search(Graph G)              
{
    int a;
    printf("您想查询哪个景点的详细信息?请输入景点编号:");
    scanf("%d",&a);
    printf(" ");
    for(int i=0;i<=10;i++)
		if(G.arcvex[i].number==a)
		{
			printf("%s\n",G.arcvex[i].name);
		       printf("%s\n",G.arcvex[i].imformation);
		}

		  
}

void ShortestPath(Graph &G,int num) 
{ 
 int v,w,i;  
 int final[NUM]; 
 int min;
   for(v=0;v<NUM;v++)
   {
    final[v]=0; 
    D[v]=G.arcs[num][v].adj;
    for(w=0;w<NUM;w++) 
	{
		p[w]=-1;
	}
   }
 
   D[num]=0;
   final[num]=1;      
 
   for(i=0;i<NUM;++i)     
   {
     min=INT_MAX;     
     for(w=0;w<NUM;++w)
     if(!final[w])   
       if(D[w]<min)   
	   {
         v=w;
         min=D[w];
	   } 
    final[v]=1;   
    for(w=0;w<NUM;++w)  
     if(!final[w]&&((min+G.arcs[v][w].adj)<D[w]))
     {
         D[w]=min+G.arcs[v][w].adj;
         p[w]=v;
     }
   }
}

void display(Graph G,int i,int j)         // 打印两个景点的路径及最短距离 
{
	int a;
	a=j;
	int n=0,waitprint[NUM];
    if(D[j]!=0)
		printf("最短的路径为:%d\n",D[j]);
	 while(p[j]!=-1)
	 {
		 for(int t=0;t<NUM;t++)
			 if(p[j]==t)
			 {
				 j=t;
				 waitprint[n]=t;
				 n++;
				 break;
			 }
			 
	 }
	 printf("%d->",i);
	 for(int s=n-1;s>=0;s--)
         printf("%d->",waitprint[s]);
	 printf("%d",a);
}


void shortestdistance(Graph G)        //要查找的两景点的最短距离
{
    int i,j; 
    printf("请输入要查询的两个景点的编号(1->10):");
    scanf("%d %d",&i,&j);
   if(i>9||i<0||j>9||j<0)
    {
        printf("输入信息错误！ ");
        printf("　　请输入要查询的两个景点的编号: \n");
        scanf("%d,%d",&i,&j);
    }
    else
   {
        ShortestPath(G,i);
        display(G,i,j); 
    }
}

void map()
{
	printf("********************************************************************************");
 	printf("\t\t\t\tsouthgate(0)\t\t\t\t\t\t");
	printf("\t\t\t/ \t \\\t\t\t\t\t\t");
	printf("\t\t\Building1(1)---Building(2) \t\t\t\t\t");
	printf("\t\t    | \t\t    | \t\t\t\t\t");
	printf("\t\t\t Building(3)---Basketball(4) \t\t\t\t\t");
	printf("\t\t    /|\\ \t    | \t\t\t\t\t");
	printf("\t\t\t  /  |  \\\t    | \t\t\t\t\t");
	printf("\t\t sports(5)--wh(6) \\ \tguanNBA(7) \t\t\t\t\t");
	printf("\t\t     |  \\  |\t    | \t\t\t\t\t");
	printf("\t\t\t     |    \\|\t    | \t\t\t\t\t");
	printf("\t\t\tsum(8)--liabrary(9)/ \t\t\t\t\t\n");
}

void message()
{
	printf("----------------------------欢迎杭州电子科技大学导游系统!-----------------------");
        printf("1.景点信息查询………请按 1 ");
        printf("2.景点最短路径查询…请按 2 ");
        printf("3.退出系统……………请按 0 \n");
        printf("学校景点列表:   \n");
		printf("0:学校南大门    ");
        printf("1:第一教学楼    ");
        printf("2:行政楼        ");
        printf("3:科技教学楼    ");
        printf("4:篮球场        ");
        printf("5:田径场        ");
        printf("6:文化活动中心  ");
        printf("7:体育馆        ");
        printf("8:综合楼        ");
        printf("9:图书馆        \n");

}

int main() 
{
	Graph G;
	initGraph(G);
      Creatgraph(G);
	  int k;
	  char ch;
	  bool flag=1;
          map();
	  while(flag)
	  {
		message();
        printf("请选择服务:\n");
        scanf(" %d",&k); 
        switch(k) 
        { 
            case 1:
                printf("进入景点信息查询:");
                search(G);
                break; 
            case 2:
                printf("进入最短路径查询:");
                shortestdistance(G);
                break; 
            case 0:
                exit(0); 
            default:
                printf("输入信息错误！");
                break; 
		}

		printf("\n是否继续查询：是，请按y；否，按任意键结束.\n");
		getchar();
		scanf("%c",&ch);
		if(ch=='y')
		   flag=1;
		else
			flag=0;
	  }
	return 0;
}