Service discovery is the process of retrieving the service most similar to the query based on the description of functional and/or non-functional semantics. The original algorithm used in literature was proposed by Paolucci et al., 2002. Some research works, propose an extension or an improvement of this algorithm to correct the matchmaking used. In this paper we present an algorithm of matchmaking that resolves the problems of Paolucci algorithm by using the shortest path algorithm which determines the optimal matching between user query and provider service. This approach is validated within a framework proposed at the end of this paper and compared with the greedy approach and the bipartite graph based matching.