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+nklog²k) work and O(log³klog^*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 kth 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.