华东交通大学 校园旅游导游
p[v][w][v]=1;p[v][w][w]=1; } }
for(u=1;u<=G->vexnum;u++) for(v=1;v<=G->vexnum;v++) for(w=1;w<=G->vexnum;w++)
if(D[v][u]+D[u][w] D[v][w]=D[v][u]+D[u][w]; for(i=1;i<=G->vexnum;i++) p[v][w][i]=p[v][u][i] || p[u][w][i]; } while(flag) { printf(\请输入出发点和目的地的编号:\ scanf(\ if(k<=0 || k>G->vexnum || j<=0 || j>G->vexnum) { printf(\景点编号不存在!请重新输入出发点和目的地的编号:\ scanf(\ } if(k==j) { printf(\出发点和目的地一样!请重新输入出发点和目的地的编号:\ scanf(\ } if(k>0 && k<=G->vexnum && j>0 && j<=G->vexnum) flag=0; } printf(\最短游览路线：%s\ if(k>j){ for(u=G->vexnum;u>0;u--) if(p[k][j][u] && k!=u && j!=u) printf(\ - 11 - 华东交通大学 校园旅游导游 } if(k for(u=1;u<=G->vexnum;u++) if(p[k][j][u] && k!=u && j!=u) printf(\printf(\printf(\总路线长%dm\\n\ 已知有n个顶点的有向图,佛洛伊德算法可以求解出每一对顶点之间的最短路径。假设使用邻接矩阵d ( i, j)来对图进行存储, d ( i, j)表示υi 到υj 之间的距离,但是该距离不一定是最短距离。佛洛伊德算法的基本思想是:为求顶点υi→υj 之间的最短距离,需要进行n次试探。首先将υ0 加入路径,考虑路径υi →υ0 →υj 是否存在,如果存在,则比较υi →υj和υi →υ0 →υj 的路径长度,取长度短的路径作为υi →υj 的路径,记作(υi ,υj ) 。接着在路径上再增加一个顶点υ1 ,比较υi→υ1 →υj 和(υi ,υj )的路径长度, 取长度短的路径作为(υi ,υj) 。不断将顶点υ2 ,υ3 , .,υn - 1加入进行试探, 最后得到的(υi ,υj )必定为υi →υj 的最短路径。若使用数组dk ( i, j)表示加入顶点k后,最短路径长度的变化情况,使用数组pk ( i, j)表示加入顶点k后,最短路径上顶点的变化情况, 这样就求得了最短路径和最短路径长度。 （3）退出函数的详细设计 对于退出函数，当游客选择了退出这一个操作的时候，程序就会调用exit(0); 函数实现退出主函数的功能。最后会提示游客，欢迎下次继续使用！ （4）数据结构的详细设计 本软件的数据结构包括3个部分： 1. 邻接矩阵 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。 - 12 - 华东交通大学 校园旅游导游 2. 顶点的结构体 typedef struct Vertex//定义图中顶点的数据类型 { int num;//景点编号 char name[30];//景点名称 char introduction[200];//景点介绍 }Vertex; 定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。 3.无向图的结构体 typedef struct //定义图的数据类型 { Vertex vexs[MAX_VERTEX_NUM];//顶点的结构体 AdjMatrix arcs;//边的邻接矩阵 int vexnum,arcnum;//顶点的个数，边的个数 }MGraph; 定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。 定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单。 （5）流程图如下： - 13 - 华东交通大学 校园旅游导游 start 创建无向图 写入无向图中 Case 3 F Case 2 F Case 1 F T T T 查找信息 最短路径 分布图 Case 4 end 四、源程序 #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #include - 14 - 华东交通大学 校园旅游导游 #include int adj; //路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息， { char name[30]; int num; char introduction[200];//简介 }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM];//景点 AdjMatrix arcs;//路径数组 int vexnum,arcnum;//景点数，路径长度记录 }MGraph; MGraph b;//全局变量 void cmd(void);//在主函数中用来调用其他应用子函数的函数声明 MGraph InitGraph(void);//用来构造学校地图的子函数 返回MGraph类型 void Menu(void);//菜单函数； void Browser(MGraph *G);//调用MGraph类型的地址，进行 void ShortestPath_DIJ(MGraph * G);//迪杰斯特拉算法求最短路径的子函数 void Floyd(MGraph *G);//佛洛伊德算法 void Search(MGraph *G);//寻找要查询的景点，并输出该景点的信息 void browse_view_distribute();//查看景点分布图 void tou(MGraph *G);//景点列表 void panduan(); //void Exit();//退出 - 15 -