Dijkstra算法描述.doc

《Dijkstra算法描述.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.Dijkstra算法描述目录一、算法概述2二、算法原理及计算22.1算法原理22.2计算过程22.3改进的算法（Dijkstra-like）分析3三、源码分析3四、接口调用3Word资料.一、算法概述Dijkstra（迪杰斯特拉）算法是典型的单源最短路径计算算法，用于解决源点到所有结点最短路径计算的问题，它采用了分治和贪心（动态规划的特殊形式）的思想搜索全局最优解。本系统采用了主流、开源的JAVA图论库——Jgrapht来解决源点到终点间所有可能路径输出的问题，它的核心计算引擎采用了一种Dijkstra-like算法，由经典的

2、Dijkstra（迪杰斯特拉）算法演化和改进而来。二、算法原理及计算2.1算法原理Dijkstra算法思想为：设是带权有向图，代表图中顶点集合，代表图中含权重的边集合。将全部顶点集合分成两组，第一组为已求出最短路径的顶点集合，用表示（初始时中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合中）；第二组为其余待确定最短路径的顶点集合，用表示。按最短路径长度的递增次序依次把集合的顶点逐个加入到集合中，约束条件是保持从源点到中各顶点的最短路径长度不大于从源点到中任何顶点的最短路径长度。算法的终止条件是集合为空集，即集合

3、的顶点全部加入到集合中。Word资料.2.2计算过程以图1为例讨论Dijkstra算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为①，逐步搜索，每次找出一个结点到源点①的最短路径，直至完成所有结点的计算。图1带权有向图记为源点①到某终点的距离，是源点①到终点某条路径的所有链路长度之和。记是源点到终点的距离。Dijkstra算法归纳如下：（1）初始化，令是已求出最短路径的顶点集合，，是其余未确定最短路径的顶点集合，，可写出：(1-1)公式1-1中，是源点①与终点的直连路径长度，而代表源点①与终点不相连,初始化结果

4、如表1所示；（2）遍历集合中的所有结点并计算。所有结点中寻找一个结点，用最小值去更新Word资料.值，并将其从集合中剔除并加入到集合中。（3）重复步骤（2），直至集合为空集。表1针对图1的最短路径计算过程步骤SUD(2)D(3)D(4)D(5)D(6)初始化①②③④⑤⑥241∞∞1①④②③⑤⑥24Add242①④⑤②③⑥231Add43①④⑤②③⑥Add31244①④⑤②③⑥2Add1245①④⑤②③⑥　2312Add表1是针对图1的详细计算步骤的中间结果。具体计算描述如下：初始化步骤：由于初始选择了源点①，因此集合只是结点①。

5、观察图1，源点①到结点②、③、④的直连路径长度分别为2，4和1，到结点⑤、⑥不存在直连边因而为。根据计算结果，集合所有结点的最小值为，因而将结点④从集合中剔除并将其加入到集合中步骤1：针对结点②，（是遍历集合的某结点，是集合新加入结点），，而，因而源点①到结点②的最小距离为2；针对结点③，（是遍历集合的某结点，是集合Word资料.新加入结点），，而，因而源点①到结点③的最小距离为4；针对结点④，是集合新加入结点，标记为Add；针对结点⑤，（是遍历集合的某结点，是集合新加入结点），，而，因而源点①到结点⑤的最小距离为2；针对结点⑥

6、，（是遍历集合的某结点，是集合新加入结点），，而，因而源点①到结点⑥的最小距离为4。其余步骤同理。所有步骤演算完毕即可得出结点1的最短路径路由信息，如图2所示。图2用Dijkstra算法得出结点1的最短路径路由表通过上述Dijkstra算法的演算步骤可发现，如需在全局中搜索最短路径的全局最优解，每个步骤必须针对其余所有结点进行一次距离的计算，以搜索出下一步可能存在的路径。因此，DijkstraWord资料.算法的计算过程实际上提供了一个全局搜索所有可能路径的思路。换句话说，Dijkstra算法想要寻找全局最短路径，首先务必搜索出

7、所有可能的路径。2.3改进的算法（Dijkstra-like）分析开源的JAVA图论库——Jgrapht通过Dijkstra-like算法搜索全局所有可能路径的计算方法实际上是基于经典Dijkstra算法的完整计算流程来实现的。但是由于Dijkstr算法先天存在明显的缺陷，Dijkstra-like算法对其进行了如下改进以满足时间复杂性、空间复杂性等计算要求：（1）Dijkstra算法在通过距离计算寻找局部最优路径过程中，将所有可能路径对比后，若发现该路径不是局部最优解则会将其丢弃。因此，Dijkstra-like算法在搜索所有

8、可能路径则需要将可能结果记录下来并参与到下一步骤的计算；（2）Dijkstr算法处理过程中，在搜索所有可能路径时需要遍历所有结点进行一次距离计算，哪怕是没有直连关系且距离为的结点也参与计算，对于网络拓朴图庞大的应用场景，这将产生大量的计算资源浪费。因此，Dijk