Dijkstra算法描述

Dijkstra算法描述

目录

一、算法概述 ................................................................................................................................... 2 二、算法原理及计算 ....................................................................................................................... 2

2.1算法原理............................................................................................................................. 2 2.2计算过程............................................................................................................................. 2 2.3改进的算法（Dijkstra-like）分析 ...................................................................................... 5 三、源码分析 ................................................................................................................................... 5 四、接口调用 ................................................................................................................................... 6

一、算法概述

Dijkstra（迪杰斯特拉）算法是典型的单源最短路径计算算法，用于解决源点到所有结点最短路径计算的问题，它采用了分治和贪心（动态规划的特殊形式）的思想搜索全局最优解。

本系统采用了主流、开源的JAVA图论库——Jgrapht来解决源点到终点间所有可能路径输出的问题，它的核心计算引擎采用了一种Dijkstra-like算法，由经典的Dijkstra（迪杰斯特拉）算法演化和改进而来。

二、算法原理及计算

2.1算法原理

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

2.2计算过程

以图1为例讨论Dijkstra算法的计算过程，即计算某源点到网络上其余各结点的最短路径，设源点为①，逐步搜索，每次找出一个结点到源点①的最短路径，直至完成所有结点的计算。

42233311221624153图1 带权有向图

记D(v)为源点①到某终点v的距离，是源点①到终点v某条路径的所有链路长度之和。记l(w,?v)是源点w到终点v的距离。Dijkstra算法归纳如下： （1）初始化，令S是已求出最短路径的顶点集合，S????，U是其余未确定最短路径的顶点集合，U????????，可写出：

?l(1,v)(1-1) D(v)????公式1-1中，l(1,v)是源点①与终点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的最短路径计算过程

步骤 初始化 1 2 3 4 5 S ① ①④ ①④⑤ ①④⑤② ①④⑤②③ ①④⑤②③⑥ U ②③④⑤⑥ ②③⑤⑥ ②③⑥ ③⑥ ⑥ D(2) 2 2 2 Add 2 2 D(3) 4 4 3 3 Add 3 D(4) 1 Add 1 1 1 1 D(5) ∞ 2 Add 2 2 2 D(6) ∞ 4 4 4 4 Add 表1是针对图1的详细计算步骤的中间结果。具体计算描述如下：

初始化步骤：由于初始选择了源点①，因此集合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（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的某结点，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为源点2211114步骤1114步骤2151415步骤3结点1的路由表目的结点下一跳距离22234344154264422312231116211415415步骤5步骤4图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 List>getAllPaths( SetsourceVertices, SettargetVertices, booleansimplePathsOnly, Integer maxPathLength) { ……

// Decorate the edges with the minimum path lengths through them MapedgeMinDistancesFromTargets = edgeMinDistancesBackwards(targetVertices, maxPathLength);

// Generate all the paths

List>allPaths = generatePaths( sourceVertices, targetVertices, simplePathsOnly, maxPathLength,

edgeMinDistancesFromTargets);

returnallPaths;

}

edgeMinDistancesBackwards()函数传入终点和最大搜索路径长度，从终点开始逐步往前搜索生成网络拓朴图中所有边距离该终点的链路长度，直至拓朴图搜索完毕或者达到最大搜索长度时结束，准备进行下一步骤计算。

generatePaths()函数传入源点、终点和最大路径长度等信息，基于上一步骤的搜索结果从源点开始逐步往后搜索到终点，直至找到该终点或者达到最大路径长度时结束。搜索过程中保存每一条存在的路径并将最终结果返回出来。

四、接口调用

List>getAllPaths(SetsourceVertices, booleansimplePathsOnly, Integer maxPathLength)

SettargetVertices,

参数列表如下：

（1）sourceVertices源点集合 （2）targetVertices终点集合

（3）simplePathsOnly是否计算自环，即自身到自身的路径 （4）maxPathLength最大路径长度。

generatePaths()函数传入源点、终点和最大路径长度等信息，基于上一步骤的搜索结果从源点开始逐步往后搜索到终点，直至找到该终点或者达到最大路径长度时结束。搜索过程中保存每一条存在的路径并将最终结果返回出来。

四、接口调用

List>getAllPaths(SetsourceVertices, booleansimplePathsOnly, Integer maxPathLength)

SettargetVertices,

参数列表如下：

（1）sourceVertices源点集合 （2）targetVertices终点集合

（3）simplePathsOnly是否计算自环，即自身到自身的路径 （4）maxPathLength最大路径长度。

本文来源：https://www.bwwdw.com/article/dit.html