The selection of the shortest path problem is one of the classic problems in the graph theory. The relationship between objects in a complex environment usually has fuzziness, hesitancy, uncertainty and inconsistency. A neutrosophic set is characterized by the degree of truth-membership, indeterminacy-membership and falsity-membership, and is more capable of capturing incomplete information. The selection of the shortest path of the neutrosophic graph based on the theory of neutrosophic set and graph theory has become a key issue. For the shortest path problem in the neutrosophic graph, in which the edge length is assigned a trapezoidal fuzzy neutrosophic number instead of a real number, a solving method based on the extended dynamic programming is proposed. The path length is compared using the score function and the accuracy function based on the trapezoidal fuzzy neutrosophic numbers. An extended dynamic programming method for solving the shortest path problem is presented to obtain the shortest path and the shortest path length. Finally, two examples are used to verify the feasibility of this method, and the comparison and analysis with the Dijkstra algorithm illustrate the rationality and effectiveness of this method. And the impact of using different sorting methods on the selection of the shortest path of the neutrosophic graph is analyzed.