Abstract: The classical Dijkstra shortest path algorithm which needs both lots of sorting operation and calculation of all points in the network is comparatively low efficient. In this paper, an indegree statistics shortest path algorithm based on probabilistic search delimitation is proposed for calculation of directed network. The algorithm adopts probabilistic search to obtain a relatively short path, and defines a resistance maximum related to label numbers of points according to the length of the path. It replaces traditional labeling calculation by indegree statistics calculation, and eliminates invalid points (points that are not included in the shortest path) in the network according to resistance maximum of points. The proposed algorithm does not include sorting operation, and simplifies the network by eliminating invalid points. A numerical example shows its advantages compared with the Dijkstra algorithm, the proposed algorithm improves the computational efficiency and has practical value.

Key words: traffic engineering, shortest path algorithm, indegree statistics, probabilistic search, invalid point

摘要： Dijkstra 经典最短路径算法包括大量的排序运算，且需要对图中所有顶点进行计算，效率较低.本文针对有向网络，提出了与概率搜索定界结合的入度统计最短路径算法.该算法通过按概率搜索得到一条较短路径，依据路径长度和有向网络结构特征确定和顶点序号相关的节点阻抗最大值；采用入度统计算法代替经典的标号算法，在计算过程中根据节点阻抗最大值，采取一定方式剔除无效顶点(不在最短路径内的顶点)，简化网络结构.本文提出的算法不需要进行排序运算，简化了运算过程，并且可以剔除大量的无效顶点，降低了网络复杂度.算例分析表明，相对于Dijkstra算法，结合概率搜索定界的入度统计算法大幅度提高了运算效率，具有实用性.

关键词: 交通工程, 最短路算法, 入度统计, 概率搜索, 无效顶点