Abstract | We present a simple parallel algorithm for the single-source shortest path
problem in planar digraphs with nonnegative real edge weights. The algorithm runs
on the EREW PRAM model of parallel computation in O((n2=+n1&=) log n)
time, performing O(n1+= log n) work for any 0<å<1/2. The strength of the
algorithm is its simplicity, making it easy to implement and presumable quite
efficient in practice. The algorithm improves upon the work of all previous
parallel algorithms. Our algorithm is based on a region decomposition of the
input graph and uses a well-known parallel implementation of Dijkstra's
algorithm. The logarithmic factor in both the work and the time can be
eliminated by plugging in a less practical, sequential planar shortest path
algorithm together with an improved parallel implementation of Dijkstra's
algorithm. |