![](https://csdnimg.cn/release/download_crawler_static/88425507/bg1.jpg)
Parallel Single-Source Shortest Paths
Kevin Kelley
Tao B. Schardl
MIT Computer Science and Artificial Intelligence Laboratory
32 Vassar Street
Cambridge, MA 02139
ABSTRACT
We designed and implemented a parallel algorithm for solving
the single-source shortest paths (SSSP) problem for graphs with
nonnegative edge weights, based on Gabow’s scaling algorithm
for SSSP. This parallel Gabow algorithm attains a theoreti-
cal parallelism of Ω(E/(V lg∆ lgE/D)) in the worst case and
Ω(E/(DlgV /DlgE/D lg Delta) with high probability on a random
graph. In practice this algorithm decent parallelism on random
graphs and outperforms a simple Dijkstra implementation on six
or more processors.
1. INTRODUCTION
The single-source shortest path (SSSP) problem on graphs with
nonnegative edge weights is a common problem in graph theory
that has been studied since the 1950s. This problem arises in a host
of real-world applications, particularly in routing.
Given a wei ghted, directed graph G = (V,E) with vertex set V =
V (G) and edge set E = E(G), a weight function w : E → R
+
, and
a starting vertex v
0
, the SSSP problem is to compute the “shortest
path weight” from v
0
to all u ∈V . The weight of a path is the sum of
the weights of edges along that path, and the shortest path weight
from u ∈ V to v ∈ V is the minimum weight for any path from u to
v, or ∞ if no path exists fr om u to v. The distance to a vertex v ∈ V
is the shortest path w eight from v
0
to v.
The canonical serial algorithm for solving the SSSP problem
on graphs with nonnegative edge weights i s Dijkstra’s algorithm,
whose pseudocode is presented in Fi gure 1. This algorithm stores
the vertices of G in a minimum priority queue Q keyed on the best
known distance to each vertex. A common implementation for this
priority queue is a k-ary heap. A vertex v has been evaluated when
all outgoing edges from v . Dijkstra’s algorithm loops over the con-
tents of Q until all vertices have been evaluated. the repeatedly
extracts from the priority queue the unevaluated vertex u with the
minimum known distance from the priority queue in line 6, exam-
ines u’s adjacency list in li ne 7, and recomputes minimum known
distances for each neighbor of u in lines 8–10. One can prove that
greedily evaluating the unevaluated vertex with minimum distance
yields the correct shortest path distances for graphs with nonnega-
tive edge weights.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
Copyright 200X ACM X-XXXXX-XX-X/XX/XX ...$10.00.
DIJKSTRA(G, w,v
0
)
1 for each vertex u ∈ V (G)
2 u.dist = ∞
3 v
0
.dist = 0
4 Q = V (G)
5 while Q 6=
/
0
6 u = EXTRACT-MIN(Q)
7 for each vertex v ∈ V(G) such that (u, v) ∈ E(G)
8 if v. dist > u. dist +w(u,v)
9 v.dist = u.dist + w(u, v)
10 DECREASE-KEY(Q,v,v.dist)
Figure 1: Pseudocode for Dijkstra’s SSSP algorithm for graphs with non-
negative edge weights. At all times, the distance of a vertex u, u. dist, is the
shortest path weight known from v
0
to u. We use a minimum priority queue
Q keyed on the distance to each vertex.
Dijkstra’s algorithm does not readily lend itself to parallelization
however, because it reli es on a priority queue. Because evaluating
the vertex at the head of the priority queue may change the order of
elements remaining within the priority queue, it is not necessarily
correct or efficient to evaluate more than the head of the priority
queue on each iteration. Substantial research has been done into
parallelizing Dijkstra’s algorithm, but these strategies often rely on
known qualities of the graph being searched.
In this paper we present a novel parallel solution to the SSSP
problem, based on Gabow’s scaling algorithm for SSSP [4]. This
algorithm makes use of a simpler data str ucture for its priority
queue, which naturally exposes available much of the parallelism
in the problem. Furthermore, the only assumption this parallel
Gabow algorithm uses is that all edge weights in the graph are in-
tegral, which is a reasonable assumption for SSSP problems being
solved on modern computers.
The remainder of this paper is organized as follows. Sec-
tion 2 presents Gabow’s original scaling algorithm, while Section 3
presents the strategy for parallelizing this SSSP algorithm. Sec-
tion 4 describes several optimizations we used in implementing
parallel Gabow. Section 5 presents some theoretical analysis for
the parallelism in parallel Gabow, while Sections 6 and 7 present
our empirical findings for the available parallelism and real-world
performance of parallel Gabow, respectively. We conclude in Sec-
tion 9.
2. GABOW’S SCALING ALGORITHM
FOR SSSP
Gabow’s al gorithm i s a classic scaling approach to the single-