c++课设报告《基于Dijkstra算法的最短路径问题求解》..docVIP

课 程 设 计 任 务 书 学院 信息科学与工程 专业 通信工程 学生姓名 *** 学号 ********* 设计题目 基于Dijkstra算法的最短路径问题求解 内容及要求： 进行类的设计与实现，解决最短路径问题。具体要求如下： 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储； 采用Dijkstra算法求从某个源点到其余各顶点的最短路径； 将上述功能作为类的成员函数实现，编写主函数测试上述功能。 进度安排： 第17周：分析题目，查阅课题相关资料，进行类设计、算法设计； 第18周：程序的设计、调试与实现； 第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。 指导教师（签字）： 年 月 日 学院院长（签字） 年 月 日 目 录 1 需求分析 - 1 - 2 算法基本原理 - 1 - 3 类设计 - 2 - 4 详细设计 - 3 - 4.1 类的接口设计 - 3 - 4.2 类的实现 - 5 - 4.3 主函数设计 - 10 - 5 DOS界面程序运行结果及分析 - 11 - 5.1 程序运行结果 - 11 - 5.2运行结果分析 - 12 - 6 基于MFC的图形界面程序开发 - 13 - 6.1 基于MFC的图形界面程序设计 - 13 - 6.2 程序测试 - 15- 6.3 MFC程序编写总结 - 17 - 7 参考文献 - 17- 1 需求分析 Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。 举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。 Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。 我们以V表示G中所有顶点的集合。图中的每一个边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。 假设E为所有边的集合，而边的权重则由权重函数w:?E?→ [0, ∞]定义。 因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。 边的花费可以想像成两个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。 已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。 这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。 到每一个终点的当前最短路径长度。它的初态为：如果从到有弧，则dist[i]为弧的权值；否则dist[i]为∞。其中，长度为dist[j]=min{dist[i]|∈V}的路径是从出发的长度最短的一条最短路径，此路径为（，）。 2 算法基本原理 根据以上分析，可以得到如下描述的算法： ①假设用带权的邻接矩阵arce[i][j]来表示带权有向图，arce[i][j]表示弧，上的权值。若,不存在，则置arce[i][j]为∞（在计算机上可用允许的最大值代替）。S为已找到的从出发的最短路径的终点的集合，它的初始状态为空集。那么，从出发到图上其余个顶点（终点）可能达到的最短路径长度的初值为： dist[i]=arce[Locate Vex(G,)][i]∈S ②选择得 dist[j]=min{dist[i]|∈V-S} 就是当前求得的一条从出发的最短路径的终点。令S=S∪{j}。 ③修改从出发到集合V-S上任一顶点可达的最短顶点长度。如果 dist[j]+arce[j][k]dist[k] 则修改dist[k]为 dist[k]=dist[j]+arce[j][k] ④重复操作②、③共n-1次。由此求得从到图上其余各顶点的最短路径是依路径长度递增的序列。 用Dijkstra算法求有向图G的顶点到其余顶点v的最短路径P[v]及其带权长度D[v]。 ? 这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。初始时，源点s的路径长度值被赋为0（d[s]=0）， 同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者是无穷大（如果路径不存在的话）。? ?? Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行到所有的d[v]都代表从s到v