method a solution for MSP can be found within the same time bound.
The problem of finding all pairs of shortest paths in a directed graph with nonnegative edge weights can be solved in O(log 2 n) time using n 3 /log n processors on a CREW PRAM [7]. Therefore, SSP can be solved within the same resource bounds. However, no efficient parallel algorithm has yet been reported for MSP in parallel. In this paper we propose an algorithm on CREW PRAM for MSP which runs in O(log 2 n) time and requires n 3 /log n processors, i.e., the bounds are same as those for solving for SSP. The bottleneck of the above algorithm is the processor and time complexity needed for computing single source shortest path. All the other steps in this algorithm use only n 2 /log n processors and run in O(log n) time.
The paper is organized as follows. Section 2 provides a quick sketch of the sequential algorithm for SSP. Section 3 describes the parallel algorithm for MSP. The theoretical background for correctness of the algorithm is discussed in Section 4. Section 5 deals with the details of the implementation of the algorithm within the time and processor bounds required for computing all pairs of shortest paths.
2. SINGLE-SINK ALGORITHM
All paths in this paper refer to directed paths unless stated otherwise. Similarly, disjoint paths refer to edgedisjoint paths. A path from vertex v 1 to v 2 is denoted by
The problem of finding a shortest pair of disjoint paths from s to a single sink v can be formulated as a the minimum-cost flow problem. In this version of the min-cost flow problem all arc capacities are unity and a total flow of value 2 must be sent from s to v such that the cost of the flow is minimized. This flow problem can be solved by two successive iterations of the shortest path algorithm [2]. For the sake of completeness a summary of the proof of the formulation of SSP as a flow problem is given in the appendix to this paper.
The algorithm for solving SSP in terms of a min-cost flow problem is sketched here, as this is crucial to the understanding of the parallel algorithm for MSP presented later in the next section.