课程设计说明书--VC++环境下D算法完成最短路径求解.docVIP

课程设计说明书 NO.1 VC++环境最短路径1、课程设计得目的 本次课程设计我门要在VC++环境的最短路径，常用得有D算法和F算法等，这次我们要应用D算法完成课程设计。Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 通过本次通过这次课程设计，我们要对上课所学得知识进行巩固，掌握图、子图、结点的度数、有向图、无向图、多重图、完全图、补图、生成子图、图的同构、路、回路、连通图、弱连通、强连通等概念及其性质；掌握图的矩阵表示，给定图的邻接矩阵会求任一结点的入度、出度和度数；一个结点到另一个结点长度为k的路径的条数；该图的可达性矩阵。 对最小生成树、最短路径、Dijkstra算法，最短路由有了更深得理解。本次课程实验，要了解最短得路由得算法，掌握Dijkstra算法，Floyd-Warshall算法等算法得概念，基本原理和思想。加深对通信网基础这门课程的理解，并且在VC++环境下进行运行，得到输出结果图，并对图进行结果与分析。课程设计要求学生独立完成2、设计方案与论证 2.1最短路径算法的分类 所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。设一有向网络G =（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有： 沈 阳 大 学 课程设计说明书 NO.2 (1)Dijkstra算法 (2)A*算法 (3)SPFA算法 (4)Bellman-Ford算法 (5)Floyd-Warshall算法 (6)Johnson算法 所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。 2.2经典Dijkstra算法的主要思想 Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：(1)初始化。起源点设置为： ds=0, ps为空;所有其他点: di=∞, pi=?;标记起源点s，记k=s,其他所有点设为未标记的。(2)检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置 lkj是从点k到j的直接连接距离。(3)选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：di=min［dj, 所有未标记的点j］点i就被选为最短路径中的一点，并设为已标记的。 (4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：i=j* (5)标记点i。如果所有点已标记，则算法完全推出，否则记k=i，转到2) 再继续。 2.3 Dijkstra算法的实现 从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。 沈 阳 大 学 课程设计说明书 NO.3 要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备