Dijkstra算法描述

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

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

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

4、源点与终点 v的直连路径长度，而 代表源点与终 点 v 不相连 , 初始化结果如表 1 所示；(2) 遍历集合 U 中的所有结点 v并计算 min D(v),D(w) l(w,v) 。所有结点 中寻找一个结点 w ，用最小值 min D (v), D (w) l(w,v) 去更新 D(v) 值，并将其从 集合U 中剔除并加入到集合 S中。(3) 重复步骤( 2)，直至集合 U 为空集。表1 针对图 1的最短路径计算过程步骤SUD(2)D(3)D(4)D(5)D(6)初始化241124Add242231Add43Add312442Add12452312Add表 1 是针对图 1 的详细计算步骤的

5、中间结果。具体计算描述如下： 初始化步骤：由于初始选择了源点，因此集合 S 只是结点。观察图 1， 源点到结点、的直连路径长度分别为 2，4 和 1，到结点、不存在直连边因而为 。根据计算结果，集合 U所有结点 D( w)的最小值为 D(4) ，因而将结点从集合 U 中剔除并将其加入到集合 S 中 步骤 1：针对结点， v 2,w 4 ( v是遍历集合 U的某结点， w是集合 S新加入结点)，D(v) D(2) 2，而D(w) l(w,v) D(4) l(4,2) 1 2 3 D(2) ，因而源点到结点的最小距离 min D(v),D(w) l(w,v) 为 2；针对结点， v 3,w 4 (

6、 v是遍历集合 U 的某结点， w是集合 S新加入结 点)，D(v) D(3) 4，而 D(w) l(w,v) D(4) l(4,3) 1 D(3) ，因而源 点到结点的最小距离 min D(v),D(w) l(w,v) 为 4；针对结点，是集合 S 新加入结点，标记为 Add；针对结点， v 5,w 4 ( v是遍历集合 U 的某结点， w是集合 S新加入结 点)， D(v) D(5) ，而 D(w) l(w,v) D(4) l(4,5) 1 1 2 D(5) ，因而源 点到结点的最小距离 min D(v),D(w) l(w,v) 为 2；针对结点， v 6,w 4 ( v是遍历集合 U 的

7、某结点， w是集合 S新加入结点)， D(v) D(6) ，而 D(w) l(w,v) D(4) l(4,6) 1 3 4 D(6) ，因而源 点到结点的最小距离 min D(v),D(w) l(w,v) 为 4其余步骤同理所有步骤演算完毕即可得出结点 1 的最短路径路由信息，如图 2 所示步骤1步骤 2步骤 3结点1的路由表目的结点下一跳距离222343441542644232125步骤 5步骤 4图 2 用 Dijkstra 算法得出结点 1的最短路径路由表通过上述 Dijkstra 算法的演算步骤可发现，如需在全局中搜索最短路径的全 局最优解， 每个步骤必须针对其余所有结点进行一次距离的

8、计算， 以搜索出下一 步可能存在的路径。因此， Dijkstra 算法的计算过程实际上提供了一个全局搜索 所有可能路径的思路。换句话说， Dijkstra 算法想要寻找全局最短路径，首先务 必搜索出所有可能的路径。2.3 改进的算法（ Dijkstra-like ）分析开源的 JAVA 图论库 Jgrapht通过 Dijkstra-like 算法搜索全局所有可能路 径的计算方法实际上是基于经典 Dijkstra 算法的完整计算流程来实现的。但是由 于 Dijkstr 算法先天存在明显的缺陷， Dijkstra-like 算法对其进行了如下改进以满 足时间复杂性、空间复杂性等计算要求：（1）Di

9、jkstra 算法在通过距离计算寻找局部最优路径过程中，将所有可能路 径对比后，若发现该路径不是局部最优解则会将其丢弃。因此， Dijkstra-like 算 法在搜索所有可能路径则需要将可能结果记录下来并参与到下一步骤的计算；（2）Dijkstr 算法处理过程中，在搜索所有可能路径时需要遍历所有结点进 行一次距离计算， 哪怕是没有直连关系且距离为 的结点也参与计算， 对于网络 拓朴图庞大的应用场景，这将产生大量的计算资源浪费。因此， Dijkstra-like 算 法每次针对结点计算时， 首先获取该结点相连的边， 只计算有直连关系的结点从 而过滤掉距离为 的一类结点，大大节约计算资源。、源码

10、分析public ListGraphPath getAllPaths(SetsourceVertices,SettargetVertices,boolean simplePathsOnly ,Integer maxPathLength )/ Decorate the edges with the minimum path lengths through them Map edgeMinDistancesFromTargets = edgeMinDistancesBackwards( targetVertices , maxPathLength );/ Generate all the path

11、sListGraphPath allPaths = generatePaths(sourceVertices ,targetVertices , simplePathsOnly , maxPathLength , edgeMinDistancesFromTargets );return allPaths ; edgeMinDistancesBackwards()函数传入终点和最大搜索路径长度，从终点开 始逐步往前搜索生成网络拓朴图中所有边距离该终点的链路长度， 直至拓朴图搜 索完毕或者达到最大搜索长度时结束，准备进行下一步骤计算。generatePaths（函） 数传入源点、 终点和最大路径长度等信息，基于上一步骤的 搜索结果从源点开始逐步往后搜索到终点， 直至找到该终点或者达到最大路径长 度时结束。搜索过程中保存每一条存在的路径并将最终结果返回出来。四、接口调用ListGraphPath getAllPaths（Set sourceVertices, Set