Let G = (V, E) be a directed graph having a non-negative cost associated with each edge. Let s in V be a special vertex called the source and W &sube V be a set of other vertices called sinks in G. In this paper, a parallel algorithm is proposed for finding a pair of edge-disjoint paths from s to each possible sink t in W such that the sum of the costs of the two paths is minimized. This algorithm has processor and time complexities same as those needed to find shortest paths from s to all sinks t in W, i.e., n3/log n processors and O(log2 n) time.