In this paper we have considered the problem of message routes evaluation in the dynamic network of mobile subscribers. The network of mobile objects is represented by a graph with the time-varying structure. The search of the optimal route at any given time has polynomial complexity. As a solution, we suggest the logical-probabilistic method to build estimates of the routes. This method allows obtaining an analytical expression of the message delivery probability function for a s-connected graph with the given dimension. In this case, the time of searching for an optimal route can be considered as a constant.