文档介绍：北京理工大学珠海学院课程设计说明书2012—2013学年第一学期题目:北理珠校园导游咨询与最短路径学院:计算机学院专业班级:软件工程5班学号:1**********学生姓名:卜博指导教师:邵珂成绩: 时间: 2012年10月26日选题五:北理珠校园导游咨询与最短路径【任务描述】1) 从北京理工大学珠海学院的平面图中选取有代表性景点(10-15个),抽象成一个无向带权图。以图中顶点表示景点,边上的权值表示两地之间距离。2) 本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径,或者根据用户指定的景点输出景点的信息。知识点:图,最短路径算法难度级:★★★★★【任务要求】1) 从北京理工大学珠海学院的平面图中选取有代表性景点(10-15个),抽象成一个无向带权图。以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。4) 区分汽车线路与步行线路。【测试数据】北理珠校园导游图(距离可估计)。【实验提示】一般情况下校园的道路是双向通行的可设校园平面图是一个无向网。顶点和边均含有相关信息。【实现功能】这个系统给用户提供查询景点,浏览路径,寻找最佳的方案到达目的地,还提供了最佳路径。【概要设计】:用的图的算法进行构造,用邻接表建立图,图的每一个顶点代表相应的景点。然后再用深度优先遍历进行搜索,查找所需的路径。再用迪杰特斯拉算法求出一个景点到其他景点之间的最佳路径。然后再用弗洛伊德算法求出要查询的出发点到目的地的最短路径。【关键词】北理珠校园导游咨询与最短路径【源代码】/*包含头文件*/#include<>#include<>/*定义符号常量*/#defineINT_MAX10000#definen10/*定义全局变量*/intcost[n][n];/*边的值*/intshortest[n][n];/*两点间的最短距离*/intpath[n][n];/*经过的景点*//*自定义函数原型说明*/voidintroduce();intshortestdistance();voidalgorithm();voiddisplay(inti,intj);voidmain(){/*主函数*/inti,j;chark;for(i=0;i<=n;i++)for(j=0;j<=n;j++)cost[i][j]=INT_MAX; cost[1][3]=cost[3][1]=3000; cost[2][3]=cost[3][2]=500; cost[2][4]=cost[4][2]=1700; cost[3][10]=cost[10][3]=2700; cost[1][10]=cost[10][1]=300; cost[2][10]=cost[10][2]=1000; cost[4][10]=cost[10][4]=4500; cost[1][4]=cost[4][1]=4800; cost[4][5]=cost[5][4]=3000; cost[4][9]=cost[9][4]=1400; cost[5][9]=cost[9][5]=4400; cost[5][7]=cost[7][5]=200; cost[5][6]=cost[6][5]=500; cost[6][7]=cost[7][6]=250; cost[7][8]=cost[8][7]=3300; cost[8][6]=cost[6][8]=3550; cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0; while(1) { printf("\n\n----------------欢迎使用北京理工大学珠海学院校园导游系统----------------\n"); printf("\n\………请按i(introduc)键\n\n"); printf("\…请按s(shortestdistance)键\n\n"); printf("\……………请按e(exit)键\n\n"); printf("\n\t学校景点代码及名称(代码:景点名称)列表:\n\n"); printf("\t1:学校东门"); printf("2:学生宿舍"); printf("3:化工楼"); printf("4:教学楼"); printf("5:荔枝园\n\n"); pr