文档介绍：实验三:校园导游咨询
设计方案简介
设计一个校园导游程序,为来访的客人提供各种信息查询服务。
1)设计你所在学校的校园平面图,
2)为来访客人提供图中任意景点相关信息的查询。
3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。
设计题目实现:
实际需求
1)设计你所在学校的校园平面图,所含景点不少于10个。以图中顶点表示校园内各景点,存放景点名称、代号、简介等信息:以边表示路径,存放路径长度等相关信息。
2)为来访客人提供图中任意景点相关信息的查询。
3)为来访客人提供图中任意景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。
2)概要设计
校园全景一览图、显示出校园的平面图。
提供校园中任意景点问路查询,即求任意两个景点之间的所有路径。
3、提供校园图中多个景点的最佳访问路线查询,即求途径这过个景点的最佳(短)路径。
;
void Map();//校园地图
void CreateGraph();//创建图
void OutputPlace();//输出景点列表
void SearchPlace();//查询景点信息
void SearchPath();//查询最短路径
void Shortpath(int i);//计算最短路径
void Output(int sight1,int sight2);//输出函数
。
Map();//显示校园整体的地图、包含学校各景点的详细位置
CreateGraph();//创建图、主要用来保存各景点信息
OutputPlace();//输出景点列表、供选择景点信息查询时使用
SearchPlace();//查询景点信息、景点的名称及介绍
SearchPath();//查询最短路径、两景点间最短距离
Shortpath(int i);//计算两景点间最短路径
Output(int sight1,int sight2);//输出两景点最短路径及信息
Main()
CreateGraph()
SearchPlace()
Map()
SearchPath()
Outputplace()
Shortpath(i);
Output(i,j);
全局变量
Graph G;
int path[NUM][NUM];
int D[NUM];
重点设计及编码
重点设计:求最短路径
编码:
void Shortpath(int num)//迪杰斯特拉算法最短路径
{
int v,w,i,t;//i、w和v为计数变量//t表示景点个数
int final[NUM]; //标志数组、用来存放顶点的信息
int min;//记录权值、最终输出路径
for(v=0;v<NUM;v++)
{
final[v]=0; //假设从顶点num到顶点v没有最短路径
D[v]=[num][v].length;//将num到其余顶点的最短路径长度初始化为权值
for(w=0;w<NUM;w++)
path[v][w]=0;//初始化从v到w的路径值
if(D[v]<MAX) //存在路径
{
path[v][num]=1; //存在标志置为一
path[v][v]=1; //自身到自身
}
}
D[num]=0;//初始化新路径
final[num]=1; //初始化num顶点属于final集合
//开始主循环,每一次求得num到某个顶点的最短路径,并将其加入到final集合
for(i=0;i<NUM;++i) // -1个顶点
{
min=MAX; //当前所知离顶点num的最近距离
for(w=0;w<NUM;++w)
if(!final[w]) //w顶点在v-s中
if(D[w]<min) //w顶点离num顶点更近
{
v=w;
min=D[w];
}
final[v]=1; //离num顶点更近的v加入到s集合
for(w=0;w<NUM;++w) //更新当前最短路径极其距离
if(!final[w]&&((min+[v][w].length)<D[w]))//不在s集合,并且比以前所找到的路径都短就更新当前路径
{
D[w]=min+[v][w].length;//更新路径
for(t=0;t<NUM;t++)
path[w][t]=path[v][t];