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

摘要： 目前研究经过必经结点集的最短路径算法多数是针对不允许存在回路的情况，少数针对存在回路的传统算法时间复杂度相对偏高。对此通过探索最优路径形成的规律，将含有大量结点的图转化为含有少量结点的图，用选择性排序法尽量少地生成路径序列分支，对这些分支进行筛选从而得到最短路径。实验结果表明，在面对数目较多的必经结点时，该算法性能将优于传统算法。

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