校园导航课程报告（采用Dijkatra算法&C++）下载_Word模板_17

选作题目描述校园导航问题计算你学校的平面图，至少包含十个以上的场所，每两个场所之间可以有不同的路径，且路长可能不同。找出从任意场所到达另一个场所的最佳路径。本题的求解如下：（1）模型分析下图为本题的路径关系，用顶点表示地点，用边来表示两点之间的连接关系，即当两个顶点之间存在边时说明两者之间存在路径。由分析可知，本题为典型的最短路径求解问题，所以本题就转换成用Dijkatra算法来计算其最短路径。（2）算法分析既然要用到图的算法，就必须先考虑到建立图的存储结构，在程序中，我们考虑用邻接矩阵的存储方式。邻接矩阵是表示图中顶点之间相邻关系的矩阵。设G=（V，E）是具有n个顶点的图，则G的邻接矩阵可表示为如下所示 A[i ,j]=Wij 若（Vi,Vj）∈E（G）或者A[i ,j]=0，∞（当不满足上述条件时）一个图的邻接矩阵表示是唯一的，所以除了需要一个二维数组来存放顶点之间的关系外，还需要一个一维数组来存放顶点的信息。所有有 private: int vexs[MaxVexNum];//顶点数组 float edge[MaxVexNum][MaxVexNum];//邻接矩阵 VexName V[MaxVexNum];//顶点信息 int n;//顶点数 int e;//边数由于每个地点之间又有自己的信息，所以有 struct VexName { string data; } 由于在Dijkstra中，我们都是用顶点的序号来进行操作的，而在之前生成的txt文件中，我们是用顶点名来表示顶点的，所以需要有一算法实现两者之间的转换。 int Graph::GetNumber(string p1)//给定顶点，输出顶点序号 { for(int i=1;i>n; //读入n,e infile>>e; for(i=1;i<=n;i++) //输入顶点信息 vexs[i]=i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) edge[i][j]=Maxfloat;//初始化邻接矩阵 for(k=1;k<=e;k++) //读入e条边，建立邻接矩阵 { infile>>i>>j>>w; edge[i][j]=edge[j][i]=w; } for(i=1;i<=n;i++) infile1>>V[i].data; } 对于本题的关键算法Dijkstra，其实现的思想是： path[v]和dist[v]表示从V0到V的最短路径及其长度。DoubleNode[i][j]表示边i，j的权，若不存在边（i，j）则DoubleNode[i][j]为无穷大。设s是一个集合，其中的每个元素表示一个顶点，从源点到这些顶点的最短路径已经给出。设顶点V1为源点，集合s刚开始仅包含了V1。数组dist[v]记录从源点到其余各点的当前最短路径，其初值dist[vi]= DoubleNode[i][j]。从v1连接的顶点中选取dist[w]为最小的顶点w。即从源点到w其直接到达的路径是最短的，把w加入到集合s中，然后调整dist中V1-s中剩余顶点的距离：拿原来的dist[v]和dist[w]+ DoubleNode[w][v]比较，取最小值赋值给dist[v]，即dist[w]=dist[v]+G->DoubleNode[v][w]。重复上述操作，直到所有的顶点都进入到集合s中。s记录了从源点到该顶点存在最短路径的顶点集合，dist[]存放了从源点到V中各点之间的最短路径，path[]是最短路径的路径组数，其中path[i]表示从源点到顶点之间的最短路径。具体算法如下： void Graph::Dijkstra(int v1) //用Dijkstra算法求无向图G的v1顶点到其他顶点v的最短路径P[v]及其权D[v] { //设G是无向图的邻接矩,边不存在，则G[i][j]=Maxint //s[v]为真当且仅当v属于s，即已求得从v1到v的最短路径 float D[MaxVexNum],P[MaxVexNum];//D[MaxVexNum]是最短路径长度集 //P[MaxVexNum]是最短路径点集 int v,i,w; float min; bool s[MaxVexNum]; //s[MaxVexNum]是标志数组，判断是否访问过 for(v=1;v<=n;v++) { //初始化s和D s[v]=false; D[v]=edge[v1][v]; if(D[v] #include #include #define Maxfloat 100000.00 //最长路径 #define MaxVexNum 50 //最大顶点数 using namespace std; struct VexName { string data; };//顶点信息 class Graph { private: int vexs[MaxVexNum];//顶点数组 float edge[MaxVexNum][MaxVexNum];//邻接矩阵 VexName V[MaxVexNum];//顶点信息 int n;//顶点数 int e;//边数 public: int GetNumber(string p1);//求得节点号 void Create(ifstream &infile,ifstream &infile1);//构造函数 void Dijkstra(int v1); }; int Graph::GetNumber(string p1)//给定顶点，输出顶点序号 { for(int i=1;i不存在，则G[i][j]=Maxint //s[v]为真当且仅当v属于s，即已求得从v1到v的最短路径 float D[MaxVexNum],P[MaxVexNum];//D[MaxVexNum]是最短路径长度集 //P[MaxVexNum]是最短路径点集 int v,i,w; float min; bool s[MaxVexNum]; //s[MaxVexNum]是标志数组，判断是否访问过 for(v=1;v<=n;v++) { //初始化s和D s[v]=false; D[v]=edge[v1][v]; if(D[v]>n; //读入n,e infile>>e; for(i=1;i<=n;i++) //输入顶点信息 vexs[i]=i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) edge[i][j]=Maxfloat;//初始化邻接矩阵 for(k=1;k<=e;k++) //读入e条边，建立邻接矩阵 { infile>>i>>j>>w; edge[i][j]=edge[j][i]=w; } for(i=1;i<=n;i++) infile1>>V[i].data; } void main() { Graph G; string startplace; ifstream infile("Graph.txt",ios::in); ifstream infile1("Place.txt",ios::in); if(!infile) { cerr<<"open error!"<>sel; switch(sel){ case 0: cout<<"退出校园导航服务"<>startplace; v=G.GetNumber(startplace); G.Dijkstra(v); cout<

                    本文档为【校园导航课程报告（采用Dijkatra算法&C++）】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

校园导航课程报告（采用Dijkatra算法&C++）

你可能还喜欢