了解： 迪杰斯特拉算法用于求解一个有向图（也可以是无向图，无向图是有向图的一种特例）的一个点（称之为原点）到其余各点（称之为周边点）的最短路径问题。算法构思很是巧妙（我这么认为），简直达到了“无心插柳柳成荫”的境界。算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第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算法制作的电子词典，能过针对不同情况很好的查找到字符完全相同或者前面部分的字符完全相同的单词，但是对于中间部分或则后面部分字符相同的单词就无法找到。对于程序的优化，我们还有很多不足地方需要改进，更需要我们学习更多的知识。
指导教师评语 总结：最短路径算法关键先把已知最短路径顶点集(只有一个源点)和未知的顶点分开，然后依次把未知集合的顶点按照最短路径(这里特别强调一下是源点到该顶点的系部教研室 意 见 路径权重和，不仅仅是指它和父结点之间的权重，一开始就是在没有这个问题弄清楚)加入到已知结点集中。在加入时可以记录每个顶点的最短路径，也可以在加入完毕后回溯找到每个顶点的最短路径和权重。