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

《c++课设报告《基于.Dijkstra算法的最短路径问题求解》[1]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、课程设计任务书学院信息科学与工程专业通信工程学生姓名***学号*********设计题目基于Dijkstra算法的最短路径问题求解内容及要求：进行类的设计与实现，解决最短路径问题。具体要求如下：（1）采用图的邻接矩阵或邻接表实现最短路径问题中图的存储；（2）采用Dijkstra算法求从某个源点到其余各顶点的最短路径；（3）将上述功能作为类的成员函数实现，编写主函数测试上述功能。进度安排：第17周：分析题目，查阅课题相关资料，进行类设计、算法设计；第18周：程序的设计、调试与实现；第19周：程序测试与分析，撰写课程设

2、计报告，进行答辩验收。指导教师（签字）：年月日学院院长（签字）年月日目录1需求分析-1-2算法基本原理-1-3类设计-2-4详细设计-3-4.1类的接口设计-3-4.2类的实现-5-4.3主函数设计-10-5DOS界面程序运行结果及分析-11-5.1程序运行结果-11-5.2运行结果分析-12-6基于MFC的图形界面程序开发-13-6.1基于MFC的图形界面程序设计-13-6.2程序测试-15-6.3MFC程序编写总结-17-7参考文献-17-1需求分析Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的

3、。算法解决的是有向图中最短路径问题。举例来说，如果图中的顶点表示城市，而边上的权重表示著城市间开车行经的距离。Dijkstra算法可以用来找到两个城市之间的最短路径。Dijkstra算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。图中的每一个边，都是两个顶点所形成的有序元素对。(u,v)表示从顶点u到v有路径相连。假设E为所有边的集合，而边的权重则由权重函数w: E →[0,∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想像成两

4、个顶点之间的距离。任两点间路径的花费值，就是该路径上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e.最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。1．如果将交通网络化成带权图，假如用顶点表示城市，边表示公路段，则由这些顶点和边组成的图可表示沟通个城市的公路图，边的权用以表示两个城市之间的距离或者表示走过这段公路所需要的时间或通过这段路的难易程度等。作为司机和乘汽车的人，自然会关心如下两个问题：（1）从甲地到乙地是否有公路？（2）

5、从甲地到乙地有几条公路，哪条公路最短或花费的代价最小？这就是我们要讨论的最短路径问题。2.迪杰斯特拉提出的一个求最短路径的算法。其基本思想是：按路径长度递增的顺序，逐个产生各最短路径。3．首先引进辅助向量dist[]，它的每一个分量dist[i]表示已经找到的且从源点到每一个终点的当前最短路径长度。它的初态为：如果从到有弧，则dist[i]为弧的权值；否则dist[i]为∞。其中，长度为dist[j]=min{dist[i]

6、∈V}的路径是从出发的长度最短的一条最短路径，此路径为（，）。-15-2算法基本原理根据以

7、上分析，可以得到如下描述的算法：①假设用带权的邻接矩阵arce[i][j]来表示带权有向图，arce[i][j]表示弧<，>上的权值。若<,>不存在，则置arce[i][j]为∞（在计算机上可用允许的最大值代替）。S为已找到的从出发的最短路径的终点的集合，它的初始状态为空集。那么，从出发到图上其余个顶点（终点）可能达到的最短路径长度的初值为：dist[i]=arce[LocateVex(G,)][i]∈S②选择得dist[j]=min{dist[i]

8、∈V-S}就是当前求得的一条从出发的最短路径的终点。令S=S∪{

9、j}。③修改从出发到集合V-S上任一顶点可达的最短顶点长度。如果dist[j]+arce[j][k]

10、长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有顶点v除s外d[v]=∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者是无穷大（如果路径不存在的话）。 -15-  Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到v的最短路径可以通过将边(u,v)添加到s到u的尾部来拓展。这条路径的长度是d[u]