2015

年

7

期

151 

基于

CUDA

的

Dijkstra

算法的设计与实现

王婷婷

西南石油大学，四川

成都

 610500 

摘要：

Dijkstra

算法是一种很有代表性的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。当节点数目很

多的时候，

Dijkstra

算法遍历的节点非常多，

计算效率很低。

本文提出基于

CUDA

的

Dijkstra

的并行算法，

将大大提高

Dijkstra

算法的计算效率。

关键词：

Dijkstra

；

CUDA

；并行算法

中图分类号：

TP311.11 

文献标识码：

A  

文章编号：

1671-5780

（

2015

）

6-0151-01 

1 

导言

最短路径算法就是求一个节点到另一个节点的路途最

短的算法，在日常生活和计算机应用中运用相当广泛。

[1]

Dijkstra

算法是一种很经典的单源最短路径算法，但其串

行算法遍历的节点多且效率低。而在大规模的计算时，我们

往往希望提高计算效率，并行算法就是一种提高效率很好地

方法。

近年来，随着计算机的发展和生活节奏的加快，并行运

算在计算机的应用中越来越重要。

NVIDIA

、

Microsoft

、

Intel

等公司都分别推出了自己的并行计算平台。

[2]

本文是在

NVIDIA

公司推出的

CUDA

平台下设计实现

Dijkstra

算法的并

行运算，以此来提高计算效率。

2 CUDA

简介

2.1 CUDA 

CUDA

（

ComputeUnifiedDeviceArchitecture

）是显卡厂

商

NVIDIA

推出的一个基于

GPU

通用计算的运算平台。它是

一种新的处理和管理

GPU

计算的硬件和软件架构，包含了

CUDA

指令集架构（

ISA

）以及

GPU

内部的并行计算引擎。

在

CUDA

的架构下，一个程序分为两个部分：

Host

端和

Device

端。

Host

端是指在

CPU

上执行的部分，而

Device

端

则是在显示芯片（

GPU

）上执行的部分。通常

Host

端程序会

将数据准备好后，复制到显卡的内存中，再由显示芯片执

device

端程序，完成后再由

host

端程序将结果从显卡的内

存中取回。

2.2 CUDA

并行运算原理

在

CUDA

架构下，

显示芯片执行时的最小单位是

thread

。

数个

thread

可以组成一个

block

。一个

block

中的

thread

能存取同一块共享的内存，而且可以快速进行同步动作。每

一个

block

所能包含的

thread

数目是有限的。执行相同程

序的

block

，可以组成

grid

。在实际运行过程中，主机内存

将原始数据传到显存中，

由

GPU

调取显存中的数据并行执行，

CPU

向

GPU

传递控制指令，运算结果由

GPU

传回显存，再传

回主机内存。

3 Dijkstra

算法

3.1 

简介

Dijkstra

算法是一种很有代表性的单源最短路径算法，

主要特点是以起始点为中心向外层层扩展，直到扩展到终点

为止。

Dijkstra

算法虽然能够求出最短路径的最优解，

但是

由于它遍历计算的节点很多，所以效率比较低。

3.2 

原理

设

G=

（

V

，

E

）

是一个带权有向图，把图中顶点集合

V

分

成两组，第一组为已求出最短路径的顶点集合（用

S

表示）

，

第二组为其余未确定最短路径的顶点集合（用

U

表示）

，按

最短路径长度的递增次序依次把第二组的顶点加入

S

中。在

加入的过程中，总保持从源点

v

到

S

中各顶点的最短路径长

度不大于从源点

v

到

U

中任何顶点的最短路径长度。

3.3 

步骤

（

1

）初始时，

S

只包含源点

v

，即最短距离为

0

。

U

包

含除

v

外的其他顶点，

U

中顶点

u

距离为边上的权。

（

2

）从

U

中选取一个距离

v

最小的顶点

k

，把

k

，加入

S

中（该选定的距离就是

v

到

k

的最短路径长度）

。

（

3

）以

k

为新考虑的中间点，修改

U

中各顶点的距离；

若从源点

v

到顶点

u

的距离（经过顶点

k

）比原来距离（不

经过顶点

k

）短，则修改顶点

u

的距离值，修改后的距离值

的顶点

k

的距离加上边上的权。

（

4

）重复步骤（

2

）和（

3

）直到所有顶点都包含在

S

中。

4 Dijkstra

算法的并行实现

4.1 

并行思路

Dijkstra

的串行算法有两层

N

次循环，

第一层循环必须

按照次序执行，不能实现并行。而第二层循环有两个

N

次的

循环，第一次循环是求数组的最小值，复杂度为

O

（

N

）

；第

二次循环是更新数组的值，复杂度也是

O

（

N

）

，所以串行的

总的复杂度为

O

（

N*N

）

。那么可以将这两次循环并行，从而

降低复杂度。

4.2 

基于

cuda

的并行实现

Dijkstra

算法是通过迭代实现。假设线程的数目为

p

，

节点的数目为

n

。将集合

V

划分成

p

个子集合，每个子集合

有

n/p

个连续的节点，与每个子集合相关的任务被分配给不

同的线程。首先是第一次循环求最小值的并行，先求出子集

中的局部最小值，其复杂度为

O

（

n/p

）

。然后后一半子集合

的最小值传送给前一半子集合，合并比较得出新的最小值，

如此循环，直到剩一个子集合为止。如果

p

为偶数，则合并

后还剩

p/2

个子集合；如果

p

为奇数，则合并后还剩

p/2+1

个子集合。这样求最小值的复杂度为

O

（

n/p+logp

）

。其次是

更新子集的并行。为每个子集分配了

n/p

个节点，则更新节

点的复杂度为

O

（

n/p

）

。

这样

Dijkstra

算法的第二层循环并

行

的

总

的

复

杂

度

为

O

（

n*

（

n/p+logp+n/p

）

）

=O

（

n*n/p+n*logp

）

。当节点数目很多时，并行运算将大大提

交计算效率。

5 

结论

本文基于

CUDA

平台通过将

Dijkstra

算法的第二层循环

实现并行运算，当节点数目很多的时候将大大提高算法的效

率。

参考文献

[1]

卢文龙，王建军，刘晓军

.

基于

CUDA

的高速并行高斯滤

波算法

[J].

华中科技大学学报：自然科学版，

2011

（

5

）

：

10-13. 

[2]

武鸿浩

.CUDA

并行计算技术在情报信息研判中的应用

[J].

信息网络安全，

2012

（

2

）

：

58-59. 

[3]

钱宸，杜震洪，曹润洲，等

.

基于

CUDA

并行的全球海洋

表面温度场等值线提取算法研究

[J].

浙江大学学报：理学

版，

2014

（

1

）

：

82-89.