课
学院 程设
信息科学与工程 *** 计
专业 学号 任务
通信工程 ********* 书
学生姓名 设计题目 基于Dijkstra算法的最短路径问题求解 内容及要求： 进行类的设计与实现，解决最短路径问题。具体要求如下： （1） 采用图的邻接矩阵或邻接表实现最短路径问题中图的存储； （2） 采用Dijkstra算法求从某个源点到其余各顶点的最短路径； （3） 将上述功能作为类的成员函数实现，编写主函数测试上述功能。 进度安排： 第17周：分析题目，查阅课题相关资料，进行类设计、算法设计； 第18周：程序的设计、调试与实现； 第19周：程序测试与分析，撰写课程设计报告，进行答辩验收。 指导教师（签字）： 年月日 学院院长（签字） 年月日 目录 1需求分析 ............................... 错误!未指定书签。
2算法基本原理 ........................... 错误!未指定书签。 3类设计 ................................. 错误!未指定书签。 4详细设计 ............................... 错误!未指定书签。
4.1类的接口设计 .................................. 错误!未指定书签。 4.2类的实现 ...................................... 错误!未指定书签。 4.3主函数设计 .................................... 错误!未指定书签。
5DOS界面程序运行结果及分析 ............... 错误!未指定书签。
5.1程序运行结果 .................................. 错误!未指定书签。 5.2运行结果分析 .................................. 错误!未指定书签。
6基于MFC的图形界面程序开发 .............. 错误!未指定书签。
6.1基于MFC的图形界面程序设计 .................... 错误!未指定书签。 6.2程序测试 ...................................... 错误!未指定书签。 6.3MFC程序编写总结 ............................... 错误!未指定书签。
7参考文献 ............................... 错误!未指定书签。
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到任何其他顶点的最短路径。
1．如果将交通网络化成带权图，假如用顶点表示城市，边表示公路段，则由这些顶点和边组成的图可表示沟通个城市的公路图，边的权用以表示两个城市之间的距离或者表示走过这段公路所需要的时间或通过这段路的难易程度等。作为司机和乘汽车的人，自然会关心如下两个问题：
（1）从甲地到乙地是否有公路？
（2）从甲地到乙地有几条公路，哪条公路最短或花费的代价最小？ 这就是我们要讨论的最短路径问题。
2.迪杰斯特拉提出的一个求最短路径的算法。其基本思想是：按路径长度递增的顺序，逐个产生各最短路径。
3．首先引进辅助向量dist[]，它的每一个分量dist[i]表示已经找到的且从源点v0到每一个终点vi的当前最短路径长度。它的初态为：如果从v0到vi有弧，则dist[i]为弧的权值；否则dist[i]为∞。其中，长度为
dist[j]=min{dist[i]|vi∈V}的路径是从v0出发的长度最短的一条最短路径，此路径为（v0，vi）。
2算法基本原理
根据以上分析，可以得到如下描述的算法：
①假设用带权的邻接矩阵arce[i][j]来表示带权有向图，arce[i][j]表示弧 vj>上的权值。若 的最大值代替）。S为已找到的从v0出发的最短路径的终点的集合，它的初始状态为空集。那么，从v0出发到图上其余个顶点（终点）vi可能达到的最短路径长度的初值为： dist[i]=arce[LocateVex(G,v0)][i]vi∈S ②选择vj得 dist[j]=min{dist[i]|vi∈V-S} vj就是当前求得的一条从v0出发的最短路径的终点。令S=S∪{j}。 ③修改从v0出发到集合V-S上任一顶点vk可达的最短顶点长度。如果 dist[j]+arce[j][k] dist[k]=dist[j]+arce[j][k] ④重复操作②、③共n-1次。由此求得从v0到图上其余各顶点的最短路径是依路径长度递增的序列。 用Dijkstra算法求有向图G的v0顶点到其余顶点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最短路径的花费。这个算法经过适当的组织因而当d[u]达到它最终的值的时候，每条边(u,v)都只被拓展一次。 算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。 ?Dijkstra(G，D，s){ ???//用Dijkstra算法求有向网G的源点s到各顶点的最短路径长度 ???//以下是初始化操作 ?????S={s}；D[s]=0；//设置初始的红点集及最短距离 ????for(alli∈V-S)do//对蓝点集中每个顶点i ?????????D[i]=G[s][i]；//设置i初始的估计距离为w ?????for(i=0;i ??????????D[k]=min{D[i]：alliV-S}；//在当前蓝点集中选估计距离最小的顶点k ??????????if(D[k]等于∞) ???????????????return；//蓝点集中所有蓝点的估计距离均为∞时， ????????????????????//表示这些顶点的最短路径不存在。 ??????????S=S∪{k}；//将蓝点k涂红后扩充到红点集 ??????????for(allj∈V-S)do//调整剩余蓝点的估计距离 ??????????????if(D[j]>D[k]+G[k][j]) ???????????????//新红点k使原D[j]值变小时，用新路径的长度修改D[j]， ?????????????//使j离s更近。 ??????????????????D[j]=D[k]+G[k][j]； ?????????} ??} 3类设计 从上面的算法分析可以看到，根据算法设计了类classSPFA，public:intn;表示图里面的点数，public:intpath[MAX][MAX];定义链接矩阵最多是1000个点，public:intdis[MAX];定义源点到其他点的距离，public:intsrc;定义源点，
c课设报告《基于Dijkstra算法的最短路径问题求解》
