A new algorithm, which exploits information from both ends of the network, is presented for the bicriterion shortest path problem. The algorithm extends efficient subpaths from both the source and the sink, using efficient possible extensions already computed to perform dominance. An outer approximation of the whole set of efficient possible extensions at a given vertex is used to eliminate non-promising path labels, even if they are locally non-dominated. A technique is provided to effectively generate the extreme efficient paths and may be used to initialize the two-ended algorithm. Both procedures can readily be extended to enumerate all the efficient labels restricted to a rectangle defined by specified lower and upper bounds on the criteria. Numerical tests performed on random graphs indicate a better performance of the algorithm with respect to the one-ended labeling algorithm, especially when the size or the density of the network increases.