To improve the reliability of the increasing network two disjoint paths should be found between a given source and a given destination. The problem of finding two minimum cost node-disjoint/edge-disjoint paths with different costs in a directed network can be formulated as a linear integer programming problem minimizing the sum of the costs on the edges in two paths, which is strongly NP-complete problem. Linear relaxation programming which relaxes the integer variables in the original programming is often applied to solve this NP problem. Comparing with linear relaxation programming, Lagrangean relaxation affords a lower bound of the objective value of original programming. Based on this a Lagrangean relaxation method for solving two disjoint paths is presented after a mathematical programming model of the problem is established. By using a modified subgradient optimization technology a new algorithm to solve the Lagrangean relaxation is put forward. The complexity of the proposed algorithm is as same as the Dijkstra’s algorithm (O(n2)). The efficiency of this algorithm is demonstrated by test examples.