Finding the #kappa# Shortest Paths in Parallel

摘要

A concurrent-read exclusive-write PRAM algorithm is developed to find the #kappa# 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 #kappa# shortest paths to a given destination vertex from every vertex of a graph with n vertices and m edges, using O(m+n#kappa#log~2#kappa#) work and O(log~3#kappa#log~*#kappa#+log n(loglog #kappa#+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 #kappa#+log n) time, and O(n log n+L) work, where L is the total length of the output.