An Efficient Distributed Shortest Path Algorithm with Hierarchically Structured Topographical Model

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.