Dijkstra算法描述.doc

Dijkstra算法描述目录一、算法概述2二、算法原理及计算22.1算法原理22.2计算过程22.3改进的算法（Dijkstra-like）分析5三、源码分析5四、接口调用6一、算法概述Dijkstra（迪杰斯特拉）算法是典型的单源最短路径计算算法，用于解决源点到所有结点最短路径计算的问题，它采用了分治和贪心（动态规划的特殊形式）的思想搜索全局最优解。本系统采用了主流、开源的JAVA图论库Jgrapht来解决源点到终点间所有可能路径输出的问题，它的核心计算引擎采用了一种Dijkstra-like算法，由经典的Dijkstra（迪杰斯特拉）算法演化和改进而来。二、算法原理及计算2.1算法原理Dijkstra算法思想为：设是带权有向图，代表图中顶点集合，代表图中含权重的边集合。将全部顶点集合分成两组，第一组为已求出最短路径的顶点集合，用表示（初始时中只有一个源点，以后每求得一条最短路径，就将该路径的终点加入到集合中）；第二组为其余待确定最短路径的顶点集合，用表示。按最短路径长度的递增次序依次把集合的顶点逐个加入到集合中，约束条件是保持从源点到中各顶点的最短路径长度不大于从源点到中任何顶点的最短路径长度。算法的终止条件是集合为空集，即集合的顶点全部加入到集合中。2.2计算过程以图1为例讨论Dijkstra算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为，逐步搜索，每次找出一个结点到源点的最短路径，直至完成所有结点的计算。图1 带权有向图记为源点到某终点的距离，是源点到终点某条路径的所有链路长度之和。记是源点到终点的距离。Dijkstra算法归纳如下：（1）初始化，令是已求出最短路径的顶点集合，是其余未确定最短路径的顶点集合，可写出： (1-1)公式1-1中，是源点与终点的直连路径长度，而代表源点与终点不相连,初始化结果如表1所示；（2）遍历集合中的所有结点并计算。所有结点中寻找一个结点，用最小值去更新值，并将其从集合中剔除并加入到集合中。（3）重复步骤（2），直至集合为空集。表1 针对图1的最短路径计算过程步骤SUD(2)D(3)D(4)D(5)D(6)初始化241124Add242231Add43Add312442Add12452312Add表1是针对图1的详细计算步骤的中间结果。具体计算描述如下：初始化步骤：由于初始选择了源点，因此集合只是结点。观察图1，源点到结点、的直连路径长度分别为2，4和1，到结点、不存在直连边因而为。根据计算结果，集合所有结点的最小值为，因而将结点从集合中剔除并将其加入到集合中步骤1：针对结点，（是遍历集合的某结点，是集合新加入结点），而，因而源点到结点的最小距离为2；针对结点，（是遍历集合的某结点，是集合新加入结点），而，因而源点到结点的最小距离为4；针对结点，是集合新加入结点，标记为Add；针对结点，（是遍历集合的某结点，是集合新加入结点），而，因而源点到结点的最小距离为2；针对结点，（是遍历集合的某结点，是集合新加入结点），而，因而源点到结点的最小距离为4。其余步骤同理。所有步骤演算完毕即可得出结点1的最短路径路由信息，如图2所示。图2 用Dijkstra算法得出结点1的最短路径路由表通过上述Dijkstra算法的演算步骤可发现，如需在全局中搜索最短路径的全局最优解，每个步骤必须针对其余所有结点进行一次距离的计算，以搜索出下一步可能存在的路径。因此，Dijkstra算法的计算过程实际上提供了一个全局搜索所有可能路径的思路。换句话说，Dijkstra算法想要寻找全局最短路径，首先务必搜索出所有可能的路径。2.3改进的算法（Dijkstra-like）分析开源的JAVA图论库Jgrapht通过Dijkstra-like算法搜索全局所有可能路径的计算方法实际上是基于经典Dijkstra算法的完整计算流程来实现的。但是由于Dijkstr算法先天存在明显的缺陷，Dijkstra-like算法对其进行了如下改进以满足时间复杂性、空间复杂性等计算要求：（1）Dijkstra算法在通过距离计算寻找局部最优路径过程中，将所有可能路径对比后，若发现该路径不是局部最优解则会将其丢弃。因此，Dijkstra-like算法在搜索所有可能路径则需要将可能结果记录下来并参与到下一步骤的计算；（2）Dijkstr算法处理过程中，在搜索所有可能路径时需要遍历所有结点进行一次距离计算，哪怕是没有直连关系且距离为的结点也参与计算，对于网络拓朴图庞大的应用场景，这将产生大量的计算资源浪费。因此，Dijkstra-like算法每次针对结点计算时，首先获取该结点相连的边，只计算有直连关系的结点从而过滤掉距离为的一类结点，大大节约计算资源。三、源码分析public ListGraphPath getAllPaths( Set sourceVertices, Set targetVertices, boolean simplePathsOnly, Integer maxPathLength) / Decorate the edges with the minimum path lengths through them Map edgeMinDistancesFromTargets = edgeMinDistancesBackwards(targetVertices, maxPathLength); / Generate all the paths ListGraphPath allPaths = generatePaths( sourceVertices, targetVertices, simplePathsOnly, maxPathLength, edgeMinDistancesFromTargets); return allPaths;edgeMinDistancesBackwards()函数传入终点和最大搜索路径长度，从终点开始逐步往前搜索生成网络拓朴图中所有边距离该终点的链路长度，直至拓朴图搜索完毕或者达到最大搜索长度时结束，准备进行下一步骤计算。generatePaths()函数传入源点、终点和最大路径长度等信息，基于上一步骤的搜索结果从源点开始逐步往后搜索到终点，直至找到该终点或者达到最大路径长度时结束。搜索过程中保存每一条存在的路径并将最终结果返回出来。四、接口调用ListGraphPath getAllPaths(Set sourceVertices, Set targetVertices, boolean simplePathsOnly, Integer maxPathLength)参数列表如下：（1）sourceVertices 源点集合（2）targetVertices 终点集合（3）simplePathsOnly 是否计算自环，即自身到自身的路径（4）maxPathLength 最大路径长度。