Dijkstra算法描述

. -

. 可修编. Dijkstra算法描述

目录

一、算法概述1

二、算法原理及计算1

2.1算法原理1

2.2计算过程2

2.3改良的算法〔Dijkstra-like〕分析5

三、源码分析6

四、接口调用7

一、算法概述

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

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

二、算法原理及计算

2.1算法原理

Dijkstra算法思想为：设(,)GVE是带权有向图，V代表图中顶点集合，E代表图中含权重的边集合。将全部顶点集合V分成两组，第一组为已求出最短路径. -

. 可修编. 的顶点集合，用S表示〔初始时S中只有一个源点，以后每求得一条最短路径，就将该路径的终点参加到集合S中〕；第二组为其余待确定最短路径的顶点集合，用U表示。按最短路径长度的递增次序依次把U集合的顶点逐个参加到S集合中，约束条件是保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。算法的终止条件是集合U为空集，即集合U的顶点全部参加到集合S中。

2.2计算过程

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

14563221312123243图1 带权有向图

记()Dv为源点①到某终点v的距离，是源点①到终点v某条路径的所有链路长度之和。记(,)lwv是源点w到终点v的距离。Dijkstra算法归纳如下：

〔1〕初始化，令S是已求出最短路径的顶点集合，S，U是其余未确定最短路径的顶点集合，U，可写出： . -

. 可修编. (1,)()lvDv (1-1)

公式1-1中，(1,)lv 是源点①与终点v的直连路径长度，而代表源点①与终点v不相连,初始化结果如表1所示；

〔2〕遍历集合U中的所有结点v并计算min(),()(,)DvDwlwv 。所有结点中寻找一个结点w，用最小值min(),()(,)DvDwlwv 去更新()Dv值，并将其从集合U中剔除并参加到集合S中。

〔3〕重复步骤〔2〕，直至集合U为空集。

表1 针对图1的最短路径计算过程

步骤 S U D(2) D(3) D(4) D(5) D(6)

初始化 ① ②③④⑤⑥ 2 4 1 ∞ ∞

1 ①④ ②③⑤⑥ 2 4 Add 2 4

2 ①④⑤ ②③⑥ 2 3 1 Add 4

3 ①④⑤② ③⑥ Add 3 1 2 4

4 ①④⑤②③ ⑥ 2 Add 1 2 4

5 ①④⑤②③⑥ 2 3 1 2 Add

表1是针对图1的详细计算步骤的中间结果。具体计算描述如下：

初始化步骤：由于初始选择了源点①，因此集合S只是结点①。观察图1，源点①到结点②、③、④的直连路径长度分别为2，4和1，到结点⑤、⑥不存在直连边因而为。根据计算结果，集合U所有结点()Dw的最小值为(4)D，因而将结点④从集合U中剔除并将其参加到集合S中 . -

. 可修编. 步骤1：

针对结点②，2,4vw〔v是遍历集合U的某结点，w是集合S新参加结点〕，()(2)2DvD，而()(,)(4)(4,2)123(2)DwlwvDlD ，因而源点①到结点②的最小距离min(),()(,)DvDwlwv 为2；

针对结点③，3,4vw〔v是遍历集合U的某结点，w是集合S新参加结点〕，()(3)4DvD，而()(,)(4)(4,3)1(3)DwlwvDlD ，因而源点①到结点③的最小距离min(),()(,)DvDwlwv 为4；

针对结点④，是集合S新参加结点，标记为Add；

针对结点⑤，5,4vw〔v是遍历集合U的某结点，w是集合S新参加结点〕，()(5)DvD，而()(,)(4)(4,5)112(5)DwlwvDlD ，因而源点①到结点⑤的最小距离min(),()(,)DvDwlwv 为2；

针对结点⑥，6,4vw〔v是遍历集合U的某结点，w是集合S新参加结点〕，()(6)DvD，而()(,)(4)(4,6)134(6)DwlwvDlD ，因而源点①到结点⑥的最小距离min(),()(,)DvDwlwv 为4。

其余步骤同理。

所有步骤演算完毕即可得出结点1的最短路径路由信息，如图2所示。 . -

. 可修编. 114114151141512214151223114151223621目的结点下一跳距离222343441542644结点1的路由表选择结点1为源点步骤1步骤2步骤3步骤4步骤5图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(

Set sourceVertices,

Set targetVertices,

booleansimplePathsOnly,

Integer maxPathLength)

{

……

// Decorate the edges with the minimum path lengths through them

Map edgeMinDistancesFromTargets =

edgeMinDistancesBackwards(targetVertices, maxPathLength);

// Generate all the paths

List> allPaths =

generatePaths(

sourceVertices,

targetVertices,

simplePathsOnly,

maxPathLength,

edgeMinDistancesFromTargets);

returnallPaths;

}

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

generatePaths()函数传入源点、终点和最大路径长度等信息，基于上一步骤的. -

. 可修编. 搜索结果从源点开场逐步往后搜索到终点，直至找到该终点或者到达最大路径长度时完毕。搜索过程中保存每一条存在的路径并将最终结果返回出来。

四、接口调用

List> getAllPaths(Set sourceVertices, Set targetVertices, boolean

simplePathsOnly, Integer maxPathLength)

参数列表如下：

〔1〕sourceVertices 源点集合

〔2〕targetVertices 终点集合

〔3〕simplePathsOnly 是否计算自环，即自身到自身的路径

〔4〕maxPathLength 最大路径长度。