New pattern domain of weighted paths has been introduced in IJCAI 2013 proceedings. The data is modeled as a directed acyclic graph whose nodes are described by means of attributes. We decided to design an efficient and scalable implementation of the proposed algorithm for weighted path computation. Our first result is that we can prove and explain that the first algorithm by Sanhes et al. is correct but incomplete w.r.t. the pattern domain specification. Then, we design an efficient algorithm that is also complete. Its performances are several orders of magnitude better than the pioneer implementation. We apply our algorithm on real environmental data to discuss the qualitative added-value of this promising pattern domain.