A concurrent‐read exclusive‐write PRAM algorithm is developed to find 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 log
2
k) work and O( logˆ3k log ˆ*k+ log n( log log k+ log ˆ*n)) time, assuming that a shortest path tree rooted at the destination is pre‐computed. 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.
