城市公交网络的最短路径算法研究

本文提出了一种基于椭圆限制区域的优化二叉堆优先级队列的改进型Dijkstra最短路径算法。此算法是在对城市交通网络空间分布特征进行统计分析的基础上,针对具体的起点、中间点以及终点,来设定合理的椭圆限制搜索区域,再以当前节点的邻接点与当前点和终点连线夹角最大作为贪婪搜索策略。最后用实例验证了算法的正确性和可行性。

Research of the the shortest path algorithm of urbanized public traffic networks

The paper proposes the improved Dijkstra shortest path algorithm,which improve the traditional operations of binary heap optimal array on the base of limiting region of using ellipse.It is based on the statistical analysis of character of city transportation space distributing,and design a reasonable limiting region of using ellipse to reduce the scale of the search of the algorithm.And it makes use of the theory that the beeline is the shortest between two points,and we get the new greedy search strategy,which is determined by the maximum degree that combined by the current node,its nearest node and destination node.Finally used the example to confirm the accuracy and the feasibility.of the algorithm.