9512.net

# Finding the k Shortest Paths in Parallel

Finding the k Shortest Paths in Parallel
Eric Ruppert
Department of Computer Science University of Toronto Toronto, Ontario, Canada M5S 1A4

Abstract. A concurrent-read exclusive-write PRAM algorithm is de-

veloped to nd the k shortest paths between pairs of vertices in an edge-weighted directed graph. Repetitions of vertices along the paths are allowed. The algorithm computes an implicit representation of the k shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m + nk log2 k) work and O(log 3 k log k + log n(log log k + log n)) time, assuming that a shortest path tree rooted at the destination is precomputed. The paths themselves can be extracted from the implicit representation in O(log k +log n) time, and O(n log n + L) work, where L is the total length of the output.

Topics: parallel algorithms, data structures

1 Introduction
The problem of nding shortest paths in an edge-weighted graph is an important and well-studied problem in computer science. The more general problem of computing the k shortest paths between vertices of a graph also has a long history and many applications to a diverse range of problems. Many optimization problems may be formulated as the computation of a shortest path between two vertices in a graph. Often, the k best solutions to the optimization problem may then be found by computing the k shortest paths between the two vertices. A method for computing the k best solutions to an optimization problem may be useful if some constraints on the feasible solutions are di cult to specify formally. In this case, one can enumerate a number of the best solutions to the simpler problem obtained by omitting the di cult constraints, and then choose from among them a solution that satis es the additional constraints. Knowledge of the k best solutions to an optimization problem can also be helpful when determining whether the optimal solution is sensitive to small changes in the input. If one of the best solutions is very di erent from the optimal solution but has a cost that is only slightly sub-optimal, it is likely that minor modi cations to the problem instance would cause the sub-optimal solution to become optimal. Sequential algorithms which compute the k best solutions to an optimization problem rst compute an optimal solution using a standard algorithm. A number of candidates for the second best solution are then generated by modifying the optimal solution, and the algorithm outputs the best candidate as the second

best solution to the problem. In general, the kth best solution is chosen from a set of candidates, each one a modi cation of one of the best k ? 1 solutions. It seems that this approach cannot be used directly to obtain parallel algorithms with running times that are polylogarithmic in k, since the best k ? 1 solutions must be known before the algorithm can compute the kth best solution. A di erent technique is used here to produce a parallel algorithm for the k shortest paths problem with a running time that is polylogarithmic in k, and in the size of the problem instance. A parallel algorithm will be developed in Sect. 3 to compute the k shortest paths to a given vertex t from every vertex of a weighted directed graph. It is assumed that the weights on the edges are positive, but the algorithm can easily be adapted to handle negative edge weights, as long as there are no negative cycles in the graph. The algorithm runs on a concurrent-read exclusive-write (CREW) PRAM. (See Karp and Ramachandran's survey 15] for de nitions of PRAM models.) The algorithm nds the k shortest paths to t from every vertex in O(log3 k log k+log n log logk+log d log d) time using O(m+nk log2 k) work, where d is the maximum outdegree of any vertex in the graph, assuming that the shortest path to t from every other vertex is given. The algorithm computes an implicit representation of the paths, from which the paths themselves can be extracted in parallel using the techniques to be described in Sect. 3.2. New parallel algorithms for the weighted selection problem and the problem of selecting the kth smallest element in a matrix with sorted columns, which are used as subroutines, are outlined in Sect. 3.3. Some applications of the k shortest paths algorithm are described in Sect. 4.

Previous Work Dijkstra's sequential algorithm computes the shortest path to a given destination vertex from every other vertex in O(m + n log n) time 12]. In parallel, the shortest path between each pair of vertices can be found using a min/sum transitive closure computation in O(log2 n) time and O(n3 logn) work on an EREW PRAM 17]. More complicated implementations of the transitive closure computation run in O(log2 n) time using o(n3 ) work on the EREW PRAM and in O(logn log logn) time on the CRCW PRAM 13]. There are no known polylogarithmic-time PRAM algorithms that nd the shortest path from one particular vertex to another using less work than the all-pairs algorithm.This transitive closure bottleneck is not avoided by the algorithm presented here: the complexity bounds on the algorithm describe the amount of additional time and work to compute the k shortest paths, once the shortest paths are known. The problem of nding the k shortest paths in sequential models of computation was discussed as early as 1959 by Ho man and Pavley 14]. Fox presents an algorithm that can be implemented to run in O(m + kn log n) time 9]. Eppstein's recent sequential algorithm 7] is a signi cant improvement. It computes an implicit representation of the k shortest paths for a given source and destination in O(m + n log n + k) time. The k shortest paths to a given destination from every vertex in the graph can be found, using Eppstein's algorithm, in O(m + n logn + nk) time. The paths themselves can be extracted from the im-

plicit representation in time proportional to the number of edges in the paths. A brief description of Eppstein's algorithm is given in Sect. 2.1. The k shortest paths problem has not previously been studied in parallel models of computation. Sequential algorithms have been developed for other variations of the k shortest paths problem. Yen 23] gives an algorithm for the more di cult problem of nding the k shortest simple paths in O(kn3) time. Katoh, Ibaraki and Mine 16] describe an O(kn2) algorithm to nd the k shortest simple paths in an undirected graph.

2 Preliminaries
Let G = (V; E) be a directed graph with n vertices and m edges, where each edge (u; v) of E has a non-negative weight w(u; v). The weight of a path in G is simply the sum of the weights of the edges that make up the path. The distance from vertex s to vertex t, dist(s; t), is de ned to be the weight of the path from s to t that minimizes this sum. A path that achieves this distance is a shortest path from s to t. The problem of nding the k shortest paths from vertex s to vertex t is to nd a set P of k s-t paths such that the weight of any path in P is no larger than the weight of any s-t path not in P . There may be several paths in P with the same weight. If there are fewer than k distinct paths from s to t, the solution set P should consist of all s-t paths. Here, paths are not restricted to being simple; a vertex may appear more than once on a path. Let T be a tree with root t that is a subgraph of G and is constructed so that the (unique) path in T to t from any vertex v is a shortest v-t path in G. The tree T is called a shortest path tree of G rooted at t. The edges of the graph which do not appear in T are called non-tree edges. Any path from a xed vertex s to vertex t can be represented by the sequence of non-tree edges along the path. For example, in the graph shown in Fig. 1(a), edges of T are shown as solid lines, and non-tree edges are shown as dashed lines. In this graph, the path s ?! c ?! a ?! f ?! b ?! t could be represented by the sequence of non-tree edges, < (s; c); (a; f) >; the rest of the path can be lled in by following the edges of T. If p is any path, let sidetracks(p) be the sequence of non-tree edges that occur along the path p. For each edge (u; v) 2 E, one can de ne a measure (u; v) of the extra distance added to the weight of a path from u to t if the edge (u; v) is used instead of taking the optimal path from u to t: (u; v) = w(u; v) + dist(v; t) ? dist(u; t): The following lemma describes some properties of this measure.

t t 2 a 1 1 c 4 d 3 2 s 2 e 1 3 2 f 4 1 a b 4 c g 0 s 3 5 d e f g 2 4 b

(a) Solid edges form the tree T

(b) Values of are shown for non-tree edges

Fig. 1. an example graph

Lemma 1 (Eppstein 7]).
weight(p) = dist(s; t) +

(i) (u; v) 0 for all (u; v) 2 E . (ii) (u; v) = 0 for all (u; v) 2 T . (iii) For any path p from s to t,

X

(u;v )

2

(u; v) = dist(s; t) +

X
(u;v ) sidetracks(p)

p

2

(u; v):

To nd the k shortest paths from s to t, it is therefore su cient to nd the P paths p which yield the k smallest values of (p) = ( )2 (u; v). If is viewed as a weight function on the edges of G, a general instance of the k shortest paths problem has now been transformed into an instance where the distance to vertex t from any other vertex is 0. From now on, the weight function will be used instead of w.
u;v p

2.1 Eppstein's Sequential Algorithm
Eppstein's sequential algorithm 7] computes an implicit representation of the k shortest paths. Each path's sidetracks sequence is represented as a modi cation of the sidetracks of a shorter path. Candidates for the kth shortest path are obtained from one of the shortest k ? 1 paths either by adding a non-tree edge to the sidetracks sequence or by replacing the last non-tree edge by another one. The algorithm constructs a new weighted directed graph G0 in which each path starting at a xed vertex s0 (and ending at any other vertex) corresponds to an s-t path of G. This correspondence is bijective and weight-preserving, so the k shortest s-t paths of G can be found by computing the k shortest paths that begin at s0 in G0, using Frederickson's algorithm 10]. It is possible that the ith shortest path is obtained by adding a non-tree edge to the (i ? 1)th shortest

path (for 2 i k), so it appears that Eppstein's algorithm cannot be directly implemented in parallel with a running time that is polylogarithmic in k.

3 A Parallel Algorithm to Compute the k Shortest Paths
The k shortest paths problem will be solved in stages. During the ith stage, paths with at most 2 non-tree edges are considered and the k shortest of these paths to t from each vertex are computed. The following lemma shows that dlogke stages will be su cient. Lemma 2. There is a solution to the k shortest paths problem in which each path has at most k ? 1 non-tree edges. Proof. Suppose there is a solution set that contains a path p with at least k non-tree edges. Consider the paths from v to t whose sequences of non-tree edges are pre xes of the sequence sidetracks(p), where the pre xes are of length 0; 1; 2; : ::; k ? 1. There are k such paths, and each one has weight no greater than the weight of p, since is non-negative. So, the set of these paths is a correct solution to the problem, and each path has at most k ? 1 non-tree edges. u t The list of edges that make up each path will not be explicitly computed in each stage. Instead, each path is represented by a binary tree structure whose leaves represent the non-tree edges along the path. The ith stage constructs the implicit representations of paths by concatenating the sidetracks sequence of two paths that have been computed in previous stages. The result of such a concatenation is stored in the data structure by creating a new node, which will be the root of the tree representing the path, and setting its children pointers to point to the roots of the two smaller paths. Thus, the tree structures representing di erent paths the data structure may share common subtrees, and the height of the trees constructed during the ith stage have height at most i. Some additional information will be stored in each node of the tree structures to allow the the computations to be performed e ciently.
i ?

3.1 The Data Structure Used by the Algorithm
i v

Let A be an array that will store the root nodes of the tree structures that represent the k shortest paths from v to t that have at most 2 non-tree edges. If there are fewer than k such paths, some of the entries in the array will be nil. Elements of the array A will be formed by concatenating the sequences of non-tree edges of two paths with at most 2 ?1 non-tree edges each. Each array element stores the following information about the path p that it represents: pointers to the two previously computed paths whose sidetracks sequences were concatenated to form p, unless p contains only a single non-tree edge, in which case this edge is stored instead,
i i v i

?

All logarithms have base 2.

the weight of the path (with respect to the weight function ), the number of non-tree edges along the path, num, the number of edges on the path up to and including the last non-tree edge, and the head of the last non-tree edge on the path (this could be nil if all edges along the path are in T). In the next section, a parallel algorithm is given for extracting the k shortest paths from this implicit representation. This is done by allocating processors to traverse the leaves of the tree structures that represent the paths to obtain the sidetracks sequences and lling in the rest of the edges along the paths by traversing branches of the tree T. The actual construction of the data structure is described in Sect. 3.3.

3.2 Extracting Information from the Data Structure
First, some preprocessing is done to the shortest path tree, T. Each vertex uses pointer jumping to locate a pointer to its ancestor 2 levels above itself, for i = 1; 2; : : :; dlog(n ? 1)e. Some of these pointers may be nil. This is done so that portions of the k shortest paths that are made up exclusively of tree edges can be traversed quickly. This computation uses O(logn) time and O(n logn) work. Suppose that the jth shortest path from v to t contains l edges. The k shortest paths from v to t can then be explicitly stored one after another in an P array P of size L = =1 l . The starting location of each path in the array P can be found by performing a pre x sum (see 15]) on l1 ; : : :; l . Suppose L= log(kn) processors are available. Each processor is assigned the task of lling in a block of the output array P of length log(kn). The processor follows the pointers in the tree data structure that represents the path, starting from the root and going to the appropriate leaf to nd the rst edge it must write into P. At each node, the num eld gives the number of edges in the subpath represented by the subtree rooted at that node, so that the processor can determine whether to go left or right at each node on its way to the leaf. When it reaches a leaf, the processor begins lling in entries of P sequentially. The portion of P that the processor must compute is made up of segments of branches of T, separated by non-tree edges. The processor can perform a linear traversal of the branches of T, copying the edges into P one by one. Whenever the processor reaches the end of a segment of tree edges, it traverses the tree data structure that represents the path, to the next leaf, which represents the next non-tree edge on the path. Once the non-tree edge has been entered into P, the processor can again start copying a segment of a branch of T into P. If the rst edge that the processor is required to enter into P is in the middle of a segment of tree edges in the path, the processor can jump to the correct point in T in O(logn) time using the ancestor pointers computed during the preprocessing of T. If a processor nishes entering one of the k shortest paths into P, it starts working on the next one. The total time to compute the output array
i j k j j k

P, including the time to preprocess T, is O(log n + log(kn)) = O(logk + log n) and the total work performed is O(n logn + L). The k shortest paths to t from every vertex v can be extracted in O(log k +log n) time using O(n logn+L ) work, where L is the total length of the output for all starting vertices v, since the preprocessing of T need only be done once. In fact, some properties of the paths can be computed without explicitly listing the edges in the path, as observed by Eppstein 7]. Suppose each edge in the graph is assigned a value from a semigroup, and the value of a path is de ned as the product of the values of the edges along the path. If the associative semigroup operation can be evaluated in constant time by a single processor, the values of the k shortest paths can be computed in the same way as the num eld of the data structure, without a ecting the performance bounds.
total total

3.3 Building the Data Structure
i v

The construction of the data structure will be performed in stages. Stage i of the algorithm will compute A for each vertex v using the arrays computed in the previous stage. First, the construction of A0 is described. The rst entry of A0 will be the path from v to t in T. It has weight 0 and contains no non-tree edges. The rest of the paths in A0 will each contain exactly one non-tree edge, so the tail of each of these edges must lie on the path from v to t in the tree T. Thus, A0 can be computed by nding the k ? 1 shortest non-tree edges (with respect to ) whose tails are on the path from v to t in T. First, the k ? 1 shortest non-tree edges whose tails are at vertex v are selected, for each vertex v in the graph. This can be done using O(log d log d ) time and O(d ) work, where d is the outdegree of v, using Cole's selection algorithm 5]. In total, this requires O(log d log d) time and O(m) work, where d is the maximum outdegree of any vertex in the graph. In addition, O(logn) time and O(n) work is used to allocate the appropriate number of processors to each vertex using a pre x sum computation. Cole's parallel merge sort 6] can be used to sort the k ? 1 smallest edges out of each vertex in O(log k) time using n(k ? 1) processors. Tree contraction is used to compute the array of the k shortest edges whose tails are on the path from each vertex v to the destination t. The tree contraction is similar to that described in 18] for computing the minimum weight ancestor of each node in a node-weighted tree. Instead of each primitive operation nding the minimum of two node weights, it computes the k smallest elements in a pair of sorted arrays, each containing k elements. This primitive operation is performed by merging the two sorted arrays, and then taking the rst half of the resulting array. Ties between edge weights can be broken according to some arbitrary lexicographic order on the edges. Each merge step can be performed in O(log logk) time and O(k) work using Borodin and Hopcroft's merging algorithm 1], so the tree contraction takes O(logn log logk) time and O(nk) work in total. The num elds of the paths found during stage 0 can be lled in as follows. First, the depth of each vertex in T is computed using tree contraction. The
v v v v v v v v

algorithm is similar to the computation of minimum ancestors in 18], except that the minimization operations are replaced by additions, and each vertex in the tree is assigned a value of 1, except the root, which has value 0. This computation uses O(logn) time and O(n) work. The value of num for any path from v to t found during stage 0 of the algorithm can then be computed easily: if the path contains the single non-tree edge (x; y), the value of num is depth(v) ? depth(x) + 1. Stage 0 of the algorithm uses O(logd log d + logk + log n loglogk) time in total, and performs O(m + nk log k) work. Now, the computation of A , for i > 0 is described. The candidate paths for inclusion in A are those paths whose sidetracks sequence is obtained by concatenating sidetracks(p1 ) and sidetracks(p2), where p1 is a path in the array A ?1 , p2 is a path in A ?1 , and w is the head of the last non-tree edge of p1 . Any sidetracks sequence formed in this way represents a legal path, since there is a path in T from the head of the last non-tree edge of p1 to the tail of the rst non-tree edge in p2. For example, in the graph of Fig. 1, combining the paths p1 = g ?! s ?! c ?! a ?! t and p2 = c ?! a ?! f ?! b ?! t produces the path g ?! s ?! c ?! a ?! f ?! b ?! t. Paths p1 containing l non-tree edges will be combined only with paths p2 which have either l or l ? 1 non-tree edges. This ensures that each path considered is distinct, since any sequence of non-tree edges can be divided into such a pair p1 ; p2 in exactly one way. In fact, it is su cient to consider only those pairs which, when concatenated, yield a path that has more than 2 ?1 non-tree edges, since the k shortest paths with at most 2 ?1 non-tree edges are already known. From among these candidates, together with the paths in A ?1, the shortest k are chosen to be the entries in A . To prove that this algorithm solves the problem correctly, it is helpful to de ne a total ordering on the paths from v to t so that an invariant describing the contents of A can be stated precisely. Paths are ordered by weight, and ties are broken in favour of the path with fewer non-tree edges. If two paths from v to t have the same weight and the same number of non-tree edges, then the lexicographic order of the sidetracks sequences is used to break the tie. This total ordering is used to select the k shortest paths for inclusion in A .
i v i v i v i w i i i v i v v i v i v

Lemma 3. The paths in A are the k smallest paths (with respect to the order ) with at most 2 non-tree edges. If there are fewer than k such paths, all of them appear in A .
v i i v i v

Proof. The computation of A0 described above ensures that the invariant is true
v p i p i

for i = 0. Assume that the invariant is true for i ? 1. Let p be any path from v to t with l non-tree edges, where 2 ?1 < l 2 . Let p1 be the portion of p up to and including the dl =2e th non-tree edge. Let w be the last vertex on p1, and let p2 be the remaining portion of p from w to t. Let p3 be the path from w to t consisting only of tree edges. The paths p1p3 and p2 each have at most 2 ?1 non-tree edges.
p i

Suppose p is one of the k smallest paths (with respect to ) from v to t with at most 2 non-tree edges. To prove the invariant, it is su cient to show that p1p3 appears in A ?1 and p2 appears in A ?1, since p will then be among the paths considered for inclusion in A . Suppose p1p3 does not appear in A ?1 . By the inductive hypothesis, there are k paths from v to t that are smaller than p1 p3 (with respect to ), each with at most 2 ?1 non-tree edges. But p1 p3 p1 p2 = p, since p3 has no non-tree edges. This contradicts the fact that p is among the k smallest paths from v to t with at most 2 non-tree edges. So, p1 p3 must be in A ?1. Now suppose p2 does not appear in A ?1 . Then there are k paths from w to t, each with at most 2 ?1 non-tree edges, satisfying r1 r2 : : : r p2. But this implies that p1r1 p1r2 : : : p1 r p1p2 = p (by the de nition of the orders and ). This is a contradiction, so p2 must be in A ?1. u t It follows from Lemmas 2 and 3 that Adlog e will contain the k shortest paths from v to t. In the rest of this section, the implementation of the computation of A on a CREW PRAM is described, and the analysis of the performance of the algorithm is completed. Using the notation introduced in the previous proof, the weight of the path formed by combining p1 and p2 is just the sum of the weights of p1 and p2 , since the weight of each tree edge is 0. The num eld is lled in similarly. Suppose that the paths of A ?1 are sorted according to the number of non-tree edges in the path, with ties broken in accordance with the ordering . Then, the candidates for inclusion in A can be found by combining each path p1 having l non-tree edges in A ?1 with the paths in two contiguous subarrays of A ?1: the portions containing paths having l or l ? 1 non-tree edges. Each subarray will already be sorted by , so the paths that result from combining the path p1 with the elements of the subarray will be sorted according to . Thus, the problem of picking the shortest k paths is now equivalent to selecting the k shortest paths from a set of 2k + 1 sorted arrays of paths, each with at most k elements (one of the arrays is A ?1 , and there are two arrays for each path p1 in A ?1 whose elements are obtained by combining p1 with other paths). If the arrays are considered to be the columns of a k (2k+1) matrix, the computation of A amounts to the selection of the k smallest elements of the matrix. If ties between two paths with the same weight that appear in di erent columns are broken in favour of the element in the leftmost column, the elements selected will be the k smallest with respect to the ordering . A PRAM implementation of Frederickson and Johnson's sequential algorithm for selection in a matrix with sorted columns 11] may be used to nd the required k paths. Lemma 4. There is an EREW PRAM algorithm that selects the kth smallest element of an r r matrix with sorted columns using O(logr(log k log k+log r)+ logk log logk) time and O(r) work if k r. The implementation is straightforward except for the subproblem of weighted selection, which can be done by modifying Vishkin's parallel selection algov i i v i v i v i w v i v i i i w i v w w w k w v v v k v v w i w k v i v i v v i v i v i w w v i v i v i v v

rithm 22]. Further details of the parallel implementation of Frederickson and Johnson's algorithm may be found in 19]. Once the k elements of A are found using the algorithm of Lemma 4, they can be sorted in O(logk) time and O(k log k) work using Cole's parallel merge sort 6]. The ith stage of the algorithm that computes the arrays A (for all vertices v) therefore uses O(log2 k log k) time and O(nk logk) work. Once the dlog ke stages of the algorithm are complete, the k shortest paths are stored implicitly in the data structure. This completes the proof of the following theorem.
i v i v

Theorem 5. Let G be a directed graph with n vertices, m edges. Let d be the

maximum outdegree of any vertex. Given the tree of shortest paths rooted at the destination vertex t, an implicit representation of the k shortest paths to t from every vertex can be computed on a CREW PRAM using O(log3 k log k + log n loglog k + log d log d) time and O(m + nk log2 k) work.

As described in Sect. 3.2, the paths can be explicitly listed using O(logk + log n) time and O(n logn + L) work, where L is the length of the output. The parallel algorithm developed here will also work on weighted directed multigraphs. The performance bounds proven above still apply unchanged. If some of the edge weights are negative, the algorithm will still work, provided there is no cycle in the graph whose total weight is negative. Lemma1 still applies in this case. Therefore, the transformation used to reduce a general problem instance to one with non-negative edge weights (de ned by ), where the distance to vertex t from any other vertex is 0, also applies to graphs with negative edge weights that have no negative cycles.

4 Applications
Two applications of the k shortest paths problem will now be described. More detailed descriptions of these applications may be found in 19]. The Viterbi decoding problem is to estimate the state sequence of a discretetime Markov process, given noisy observations of its state transitions. This problem has applications in communications (see 8]). The list Viterbi decoding problem is to compute the k state sequences that are most likely to have occurred, given a particular sequence of observations. Sequential algorithms exist that construct a weighted directed acyclic graph in which each path between two xed vertices describes a possible state sequence 8]. The weight of the path corresponding to a state sequence is equal to the conditional probability that it occurred, given the observations. Sequential algorithms for this problem have appeared previously 20, 21], and a straightforward parallel implementation was described by Seshadri and Sundberg 20]. The parallel k shortest paths algorithm can be applied to this graph to solve the list Viterbi decoding problem on a CREW PRAM using O(log2 s + log(sT) log logk + log3 k log k) time and O(s3 T + sTk log2 k) work, where s is the size of the state space of the Markov

process and T is the length of the observation sequence. This is the rst parallel algorithm for this problem that runs in polylogarithmic time. The quickest paths problem 4] is a generalization of the shortest path problem. It is used to model the problem of transmitting data through a computer network. Each edge of a directed graph is assigned a positive capacity and a nonnegative latency. The capacity c(p) of a path p is de ned to be the minimum capacity of any edge on the path. The latency l(p) is the sum of the latencies of the edges of p. The time to transmit bits of data along a path p is l(p)+ =c(p). The k quickest paths problem is to compute the k paths that require the least time to transmit a given amount of data between a given pair of vertices. If all edge capacities are equal, the problem reduces to the k shortest paths problem. Subpaths of quickest paths need not be quickest paths themselves, so the approaches used to solve shortest path problems are not directly applicable to quickest path problems. Sequential algorithms for the k quickest paths problem have been studied previously 2, 3, 19]. The problem can be solved by rst nding the k shortest paths (with respect to latency) that have capacity at least c, for each edge capacity c, and then choosing from among them the k paths that have the shortest overall transmission time 3]. Repeated use of the parallel k shortest paths algorithm yields a CREW PRAM implementation of this approach that nds the k quickest paths to a given destination vertex t from every vertex v. For an n-node graph with m edges and r distinct edge capacities, the parallel algorithm runs in O(log2 n logr + log3 k + log n loglogk) time using O(n2m log n logr + rnk log2 k) work.

Acknowledgements
I thank my advisor Faith Fich for many invaluable discussions throughout the development of this paper. Derek Corneil provided helpful comments on the presentation of this material. Financial support was provided by the Natural Sciences and Engineering Research Council of Canada.

References
1. A. Borodin and J. E. Hopcroft. Routing, merging and sorting in parallel models of computation. Journal of Computer and System Sciences, 30:130{145, 1985. 2. Gen-Huey Chen and Yung-Chen Hung. Algorithms for the constrained quickest path problem and the enumeration of quickest paths. Computers and operations research, 21(2):113{118, 1994. 3. Y. L. Chen. Finding the k quickest simple paths in a network. Information Processing Letters, 50(2):89{92, April 1994. 4. Y. L. Chen and Y. H. Chin. The quickest path problem. Computers and Operations Research, 17(2):153{161, 1990. 5. R. Cole. An optimally e cient selection algorithm. Information Processing Letters, 26:295{299, January 1988. 6. R. Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770{785, August 1988.

7. David Eppstein. Finding the k shortest paths. In Proc. 35th IEEE Symposium on Foundations of Computer Science, pages 154{165, 1994. 8. G. David Forney, Jr. The Viterbi algorithm. Proceedings of the IEEE, 61(3):268{ 278, March 1973. 9. B. L. Fox. Calculating kth shortest paths. INFOR; Canadian Journal of Operational Research, 11(1):66{70, 1973. 10. Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104:197{214, 1993. 11. Greg N. Frederickson and Donald B. Johnson. The complexity of selection and ranking in X + Y and matrices with sorted columns. Journal of Computer and System Sciences, 24:197{208, 1982. 12. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596{615, 1987. 13. Y. Han, V. Pan, and J. Reif. E cient parallel algorithms for computing all pair shortest paths in directed graphs. In 4th Annual ACM Symposium on Parallel Algorithms and Architectures, pages 353{362, 1992. 14. Walter Ho man and Richard Pavley. A method of solution of the Nth best path problem. Journal of the ACM, 6:506{514, 1959. 15. Richard Karp and Vijaya Ramachandran. Parallel algorithms for shared-memory machines. In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, pages 871{941. Elsevier, 1990. 16. N. Katoh, T. Ibaraki, and H. Mine. An e cient algorithm for K shortest simple paths. Networks, 12:411{427, 1982. 17. Richard C. Paige and Clyde P. Kruskal. Parallel algorithms for shortest paths problems. In Proceedings of the International Conference on Parallel Processing, pages 14{20, 1985. 18. Margaret Reid-Miller, Gary L. Miller, and Francesmary Modugno. List ranking and parallel tree contraction. In John H. Reif, editor, Synthesis of Parallel Algorithms, chapter 3. Morgan Kaufmann, 1993. 19. Eric Ruppert. Parallel algorithms for the k shortest paths and related problems. Master's thesis, University of Toronto, 1996. 20. Nambirajan Seshadri and Carl-Erik W. Sundberg. List Viterbi decoding algorithms with applications. IEEE Transactions on Communications, 42(2/3/4 Part I):313{323, 1994. 21. Frank K. Soong and Eng-Fong Huang. A tree-trellis based fast search for nding the N best sentence hypotheses in continuous speech recognition. In Proceedings of the International Conference on Acoustics, Speech and Signal Processing, volume 1, pages 705{708, 1991. 22. Uzi Vishkin. An optimal parallel algorithm for selection. In Advances in Computing Research, volume 4, pages 79{86. JAI Press, 1987. 23. Jin Y. Yen. Finding the K shortest loopless paths. Management Science, 17(11):712{716, July 1971.

a This article was processed using the L TEX macro package with LLNCS style