数据结构课程设计报告 - 最短路径C++ - 图文

青岛理工大学琴岛学院教务处

2011 年 7 月 7日

学 生 课题名称 设计地点 aaaa 求解最优交通路径 指导教师 设计时间 7-A-105 （1）用二进制给每个字符进行编码，树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列和作为各个对应的字符的编码，将输入的字符用“0” “1”表示出来，译码的过程是输入“0”“1”代码显示输出相对应的字符。 利用弗洛设计目的 (2) 要求学生根据离散数学或数据结构中最短路径算法进行程序编写。伊德算法结合实际情况，通过以每个点为源顶点求出每对定点之间的最短路径。通过二维数组A存放当前最短路径长度，最后输出对应的最短路径长度。 （3）制作一个查阅词典的雏形，主要利用串的匹配算法KMP算法并结合文件的一些知识。设置目标串和模式串的字符比较，查找出需要查找的单词或者是与需要查找的单词有部分的相同字母的单词。 aaa 2011/6/27-2011/7/8

设计内容（包括设计过程、主要收获、存在问题、解决措施、建议，不少于2000字） 一、 运行环境 Microsoft Visual C++6.0不仅仅是一个编译器。它是一个全面的应用程序开发环境。Visual C++采用的框架是MFC。MFC不仅仅是一个类库。MFC 是一个很大的、扩展了的 C++ 类层次结构，它能使开发 Windows 应用程序变得更加容易。 二、 系统流程图 开始 进入查询界面 输入要查询的两个城市编号m_v0,m_v1 查看各城市对应的编号 输入要查询的两个城市 接收城市编号CreatUDN()创建界面 判断前后两次输入的编号是否在查询范围ShortestPath( )计算出最短路径及距离Output()输出起点和终点 N Y 输出最短路径及距离 输出两站点路径及最短距离 否 是 是否继续查询选择 结束 退出

三、 函数及变量说明 (一) 相关函数 （1）首先创建CreatUDN( )函数生成一个拥有25个城市，30条公路的交通图，并录入两城市之间的权值即距离，其中顶点对应于城市，边对应于城市间直接通路，根据实际问题，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。创建对话框提示用户输入发出城市和终到城市的序号，再调用ShortestPath( )函数求出最短路径，由Output( )函数输出结果。 （2）ShortestPath( )利用了数据结构中图论中的最短路径相关的弗洛伊德算法。Output()函数把计算的结果格式化输出。 （二）对于带有权值的网络图求解最小路径问题，一般有两种算法：迪杰斯特拉和弗洛伊德算法，前者是求解单源最短路径问题，后者是求全源最短路径问题。就本程序而言用迪杰斯特拉比较简单，因而采用前者。 （三）具体实现 1. CreatUDN( )函数生成一首先通过个拥有25个城市，30条公路的交通图 根据用户输入的顶点数和边数生成一个相应的交通图，其中顶点对应于城市，边对应于城市间直接通路。 void CreateUDN(v,a) /*造图函数 向图*/ int v,a;构造无图 { int i,j; G.vexnum=v; G.arcnum=a; for(i=0;i

2. 调用narrate( )函数输出提示信息，提示用户输入发出城市和终到城市的序号：narrate( )函数把能够进行计算的城市列表按简单的格式进行输出 void narrate() /*说明函数*/ { int i,k=0; printf(\欢迎使用最优交通路径程序!***************\\n\ printf(\ 制作人：李盟 高东 孙鹏鹏\\n\ printf(\城市列表如下:\\n\\n\ for(i=0;i<25;i++) { printf(\输出城市列表*/ k=k+1; if(k%4==0) printf(\} 3.用ShortestPath( )函数求出最短路径具体功能实现及相应的迪杰斯特拉算法 为了便于ShortestPath( )函数的计算，在生成的交通图中所有的通路都是双向的，即如果A城市到B城市有直接通路，且里程为k千米，则B城市到A城市也有直接通路，并且里程同样为k千米。 void ShortestPath(num) /*最短路径函数 可以查询距离最近的点*/ int num; { int v,w,i,t; int final[25];/*final成员变量表示常量，只能被赋值一次，赋值后值不再改变。*/ int min; for(v=0;v<25;++v) { final[v]=0;D[v]=G.arcs[num][v].adj; for(w=0;w<25;++w) P[v][w]=0; if(D[v]<20000) {P[v][num]=1;P[v][v]=1;} } D[num]=0;final[num]=1; for(i=0;i<25;++i) { min=20000; for(w=0;w<25;++w) if(!final[w]) if(D[w]

4.output 函数输出结果 格式化输出 void output(city1,city2) /*输出函数*/ int city1; int city2; { int a,b,c,d,q=0; a=city2; if(a!=city1) { printf(\从%s到%s的最短路径是\ printf(\最短距离为 %dkm.)\\n\\t\ printf(\ d=city1; for(c=0;c<25;++c) { gate:; /*标号，可以作为goto语句跳转的位置*/ P[a][city1]=0; for(b=0;b<25;b++) { if(G.arcs[d][b].adj<20000&&P[a][b]) { printf(\ P[a][b]=0; d=b; if(q%8==0) printf(\ goto gate; } } } } 5.退出main( )函数，程序结束。 void main() /*主函数*/ { int v0,v1; CreateUDN(25,30); narrate();/*引导界面输出*/ printf(\请选择起点城市（0～24）：\\n\ scanf(\ printf(\请选择终点城市（0～24）：\\n\ scanf(\ ShortestPath(v0); /*计算两个城市之间的最短路径 在此函数中使用迪杰斯特拉算法 output(v0,v1); /*输出结果*/ printf(\请按任意键退出...\\n\ getchar(); }

了解： 迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列（如果这个有向图中有环1-2-3-1算法岂不是永无终结之日了？？！！），但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。 算法把一个图（G）中的点划分成了若干部分： 1）：原点（v）； 2）：所有周边点（C）； 另外有一个辅助集合S，从v到S中的点的最短路径已经求得。S的最初状态是空集。 这样就可以进一步划分图（G）： 1）：原点（v）； 2）：已求出v至其最短路径的周边点（S）； 3）：尚未求出v至其最短路径的周边点（Other=C-S）； 算法的主体思想： A、找到v——Other所有路径中的的最短路径vd=v——d（Other的一个元素）； B、找到v——S——Other所有路径中的的最短路径vi=v——i（Other的一个元素）； C、比较vd和vi如果vd<=vi则将d加入S且从Other中删除，否则将i加入S且从Other中删除。 重复以上步骤直至Other为空集。 我们求得的最短路径是升序排列的，那为什么下一条最短路径就存在于v—— 用到了贪心的策略 找最短的未拓展节点，加入已拓展部分 然后再根据此节点，重新更新未拓展部分 就是通过一个方法，找到起始位置到目标位置的最优化路线 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等 Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。 其采用的是贪心法的算法策略

四． 调试分析（调试过程中出现的问题及处理方式） A. 调试出现的界面 1) 进入程序弹出查询信息对话框如图2： 图2 2) 输入查询信息，显示路径长度及最短路径，如果输入代号不在0~24之内，提示出错。 图3

图4 B．出现的问题及解决方式 1) 1、 开始时最短路径由二维数组表示，路径的输出比较困难，后来我将其改为一维数组，可以方便地输出。 2、 迪杰斯特拉算法的时间复杂度均为O(n*n) 出现问题：运行程序后，无法弹出对话框。弹出对话框后，在查询最短路径时，第一次查询正常，而之后的查询最短路径在之前的基础上不断添加。 分析问题：对话框不显示，应该是缺少相关的命令。而路径出错，应该增加对应的语句 使每次查询，显示路径的对话框能过刷新一次。 3、

2) 查询成功后，可修改城市代号反复查询。 五、附加（对另外两个程序的理解） 六、总结 在设计的过程中遇到了许多问题，可以说得是困难重重，毕竟这是不可避免的，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。加深了我们对相关算法的理解，巩固了相关知识。把课堂上讲的理论付诸实践，丰富课 程的趣味性，学以致用。在界面方面实行了非常人性化的方式。因为通常清楚程序的人，知 道怎么操作以及该输入什么，而不清楚的人却有很大可能在细节方面输入错误导致程序运行失败，或是根本不知道应该怎么输入。所以，尽可能的人性化的设计是非常有必要的，让不懂程序的人也可以正确的操作运行。另外，在输入城市编号时，最初设计的是输入城市的名 称，通过参数传递在View类添加代码，然后显示时也输出城市，在接收完城市名称后，先将CString类型的城市名称，转化为char类型的，在转化为unsigned int型，进行参数传递，经过(WPARAM wParam,LPARAM lParam)，最后输出时再转换成CString型的。由于CString无法直接转换成char型，经过强制类型转换后，再转换回来的字符不再是当初预期的结果。于是，放弃了城市名字的相关编辑，在输入输出中显示的都只是城市序号，也算是该程序的一大缺失。另外，由于时间关系及水平有限，没有实现，在用户查询完后，没有实现在界面的地图上将用户查询的路线在地图上描绘出来,是程序不足的一方面。 经过这次课程设计，对于哈夫曼编码，弗洛伊德算法以及KMP算法有了很好的巩固，同时也加深了相关理解。对于哈夫曼编码，能够很好的通过字符对应的权值，对其进行编码,然后根据编码的情况进行译码。对于KMP算法制作的电子词典，能过针对不同情况很好的查找到字符完全相同或者前面部分的字符完全相同的单词，但是对于中间部分或则后面部分字符相同的单词就无法找到。对于程序的优化，我们还有很多不足地方需要改进，更需要我们学习更多的知识。

指导教师评语 总结：最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的系部教研室 意 见 路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。

本文来源：https://www.bwwdw.com/article/16wo.html