A large variety of problems in different fields, including the problems of the creation of optimal solutions of different kinds, can be formulated in graph theory language in the form of search tasks at given graphs of optimal paths of special character. Many results in these courses are now obtained which refer to classical graph theory. In this theory, a graph is assumed to be a deterministic object and there are no any uncertainties (fuzzinesses) in its description and in the description of its functioning process. Nowadays, science has come to the realization that the majority of our knowledge and links with the external world do not correspond to formerly established classical notions about them. New approaches to these areas are now being developed, which imply principal impossibility to do without fuzzinesses that are accepted as a reality of human existence. This requires the development of complex of concepts and methods which in, this fuzziness should be taken into account really in practical applications. In the proposed article, the tasks of searching optimal paths according to some criteria in the frames of currently accepted fuzzy graph model are considered. When solving the problem of the shortest paths, the rule of choosing the “best” arc is introduced and motivated. The method of solving the tasks with the use of the design of oriented graph path tree is proposed. The notion of path feasibility in fuzzy graph is introduced, the feasibility is evaluated as the probability of path real existence in given graph. The method for calculation of path feasibility, based on the reduction of belonging degree of each arc in the path of graph path to its probability, is proposed. The task on the search of path with maximum feasibility is solved on this basis.