## Parallel Algorithms for the *k* Shortest Paths and Related Problems

## Abstract

A parallel algorithm is developed to find the *k* shortest paths
between pairs of vertices in an edge-weighted directed graph.
The concurrent-read exclusive-write PRAM is used as the model of
computation. The algorithm computes an implicit representation of the
*k* shortest paths to a given destination vertex from each vertex of a
graph with *n* vertices and *m*
edges, using *O*(*m+nk*log^{2}*k*) work and
*O*(log^{3}*k*log^{*}*k*+log *n*(loglog *k*+log^{*}*n*)) time, assuming that a
shortest path tree
rooted at the destination is precomputed.
Parallel algorithms are also described for a weighted version of the
problem of selecting an element of given rank from an unsorted
array and for the selection of the *k*th smallest element in a matrix
with sorted columns.

The *k* shortest paths algorithm is applied to obtain a parallel
implementation of a dynamic programming algorithm for the list Viterbi
decoding problem, where one must find the most probable state
sequences of a Markov process, given noisy observations of the state
transitions.
Algorithms are developed for the problem of computing quickest paths
for the transmission
of data through a graph, where the time to send data across an
edge depends on the capacity of the edge and on its latency.