In many branch-and-price algorithms, the column generation pricing problem consists of computing feasible paths in a network. In this paper, we show how, in this context, path reduced costs can be used to remove some arcs from the underlying network without compromising optimality and we introduce a bidirectional search technique to compute these reduced costs. This arc elimination method can lead to a substantial speedup of the pricing process and the overall branch-and-price algorithm. Special attention is given to variants of shortest path problems with resource constraints. Computational results obtained for the vehicle routing problem with time windows show the efficiency of the proposed method.