关键词: 最优路径, Dijkstra算法, 单边因子, 选择性排序

Abstract: At present, most of the shortest path algorithms that pass through the necessary set of nodes are aimed at the situation where no loops are allowed, and a small number of traditional algorithms for the loop have high time complexity. In this regard, this paper explores the law of the formation of the optimal path, the graph containing a large number of nodes is transformed into a graph containing a small number of nodes, the path sequence branch is generated as little as possible by selective sorting, these branches are filtered to obtain the shortest path. The analysis of the algorithm and experimental results show that the performance of the algorithm is superior to that of the traditional algorithm in the face of a large number of necessary nodes.

Key words: shortest path, Dijkstra’s algorithm, one-sided factor, selective sorting