In-degree Statistics Shortest Path Algorithm Based on Probabilistic Search Delimitation
Wei Deng · Journal of Transportation Systems Engineering and Information Technology · 2011
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.