This paper presents a (d, c)‐minimal paths based algorithm to evaluate the reliability index R
(
d,c
), defined as the probability that the source distributes a demand d successfully to the destination with the total distribution cost not exceeding budget constraint c. The proposed algorithm employs two schemes to reduce the search space of (d, c)‐minimal paths: (1) by proposing some conditions, an improved method for solving (d, c)‐minimal paths is developed; (2) an existing decomposition technique is applied to limit the search space. Computational results show a clear advantage of the proposed algorithm in seeking (d, c)‐minimal paths.