呙维, 龚健雅, 朱欣焰. 一种基于层次拓扑模型的分布式最短路径算法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(7): 864-868.
引用本文: 呙维, 龚健雅, 朱欣焰. 一种基于层次拓扑模型的分布式最短路径算法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(7): 864-868.
GUO Wei, GONG Jianya, ZHU Xinyun. An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 864-868.
Citation: GUO Wei, GONG Jianya, ZHU Xinyun. An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 864-868.

一种基于层次拓扑模型的分布式最短路径算法

An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model

  • 摘要: 为整合已有的不同地点的GIS路径服务,实现网络拓扑数据的全局最短路径查询,提出了一种基于层次拓扑模型的分布式最短路径算法,并且着重针对网络传输和计算效率问题,提出了两种优化方法。

     

    Abstract: The route computation module is one of the most important functional blocks in a dynamic route guidance system.Although various algorithms exist for finding the shortest path,they are faced with the networks in the same server without distributed environment.We present an efficient distributed hierarchical routing algorithm that finds a near-optimal route and evaluate it on a large city road network,which consists of a lot of small networks which are placed on different servers.Solutions provided by this algorithm are compared with the stand-alone traditionally by hierarchical routing solutions to analyze the same and different points.We propose two novel but simple heuristic to substantially improve the performance of the hierarchical routing algorithm with acceptable loss of accuracy.The improved distributed hierarchical routing algorithm has been found to be faster than a local A* algorithm.

     

/

返回文章
返回