An efficient parallel algorithm for shortest paths in planar layered digraphs

INTRODUCTION Computing shortest paths in directed graphs isa fundamental optimization problem with applica-tions to many areas of computer sciences and op-eration research (Bellman, 1958; Coremen, 1990;Cohen, 1993). Given a digraph G with non-negativeweights on its edges and two vertices s and t of G,the single-pair shortest path problem consists ofdetermining a directed path from s to t with mini-mum total weight. Among the well-known sequential algorithmsfor this problem is the classic…

An efficient parallel algorithm for shortest paths in planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.