大型复杂网络中最短路径查询的优化方法

An Effective Method of Shortest-path Search in Complicated Road Network

本文通过对Dijkstra算法和A*算法的介绍,并分析它们在大型复杂网络中应用时所存在的瓶颈问题,提出了基于网络分块的优化思想。通过对复杂网络的分块处理,筛选出最可能包含最短路的区域块,由于缩小了检索的区域,这将有效的减少计算最短路径的时间。

With introduction in details of Dijkstra and A＊ algorithm,this article analyzes the bottlenecks of these two algorithms when applied in huge and complicated road network,finally,an effective method based on network block is proposed.By sub-block processing on complicated road network,we can get parts of the blocks that content the shortest path as much as possible,as the search area is narrowed,the time taken in calculating the path is sure to be reduced.