Computer Science ›› 2016, Vol. 43 ›› Issue (6): 188-193.doi: 10.11896/j.issn.1002-137X.2016.06.038

Previous Articles     Next Articles

Shortest Path Searching Algorithm Based on Geographical Coordinates and Closed Attribute in Road Network

GU Ming-hao and XU Ming   

  • Online:2018-12-01 Published:2018-12-01

Abstract: Concerning the problem of finding the shortest path in the large scale city road network,this paper proposed an algorithm based on the Edge Clustering Tree and Minimal Closed Lattice to achieve the goal of quick searching.Firstly,the city road network is proprocessed,i.e. using the definition of the MCL to classify the road network.Then ETC is used to storage the MCL .Eventually,depending on the idea of the virtual path(the shortest distance between two points is the straight line distance),combining the attribute of MCL planarity of the road network and taking advantage of the ECT will dramatically reduce the visits to dud nodes.So this kind of algorithm really reduces the time complexity and achieves the purpose of quick searching.The theoretical analysis and the simulation experiment demonstrate that the storage space of ECT is 45.56% less than the PCDC algorithm and 24.35% less than TNR.In the aspect of storage,ECT is slightly better than SILC.Besides,the query efficiency of the MCL is 15.6% faster than that of the SPB.The results of the experiment suggest that the MCL algorithm based on ETC storage can improve the query efficiency.

Key words: Minimal closed lattice(MCL),Shortest path,Virtual path,Edge clustering tree(ECT),Preprocessing

[1] Dijkstra E W.A note on two Problems in connectionwithgraphs[J].Numerische Mathematik,1959,1(1):269-271
[2] Samet H,Sankaranarayanan J,Alborzi H.Sealable network distance browsing in spatial databases[C]∥The 8th SIGMOD ACM Conference.2008:43-54
[3] Klein P N,Mozes S,Weimann O.Shortest Paths in direeted Planar graphs with negative lengths:Aline-space time algorithm[J].ACM Transactions on Algorithms,2010,6(2):1-13
[4] Papadias D,Zhang J,Mamoulis N,et al.Query processing inspatial network databases [C]∥The 3rd VLDB.2003:802-813
[5] Cho H J,Chung C W.An efficient and scalable approach to CNN queries in a road network[C]∥The 5th VLDB.2005:865-876
[6] Sanders P,Sehultes D.Highway hierarchieshasten exact shortest path queries[C]∥13th Annual European Symposium2005 .Palma de Mallorca,Spain,October 2005:568-579
[7] Geisberger R,Sanders P,Sehultes D,et al.Con-Traction hierarchies[C]∥Faster and Simpler Hierarchical Routing in Road Networks.WEA,2008:319-333
[8] Bast H,Funke S,Matijevie D.Transit:ultrafast shortest-Path queries with linear-time Preprocessing[C]∥The 9th DIMACS Implementation Challenge.2006:175-192
[9] Deng Ding-xiong.Shortest Path Queries on Road Networksbased on Pre-Computation Techniques [D].Shanghai:FuDan University,2011
[10] Lee K C K,Lee W C,Zheng Bai-hua,et al.ROAD:A New Spatial Object Search Framework for Road Networks[J].IEEE Transactions Onknowledge and Data Engineering,2012,4(3):547-560
[11] Wang Shi-ming.Research and Realization of the Shortest Path Algorithm within Topical Urban Road Network[D].Shandong:Shandong University,2012
[12] Lu Zhao,Shi Jun.Design and Implementation of parallel shortest path search algorithm[J].Computer Engineering and applications,2010,6(3):69-71(in Chinese) 卢照,师军.并行最短路径搜所算法的设计与实现[J].计算机工程与应用,2010,6(3):69-71
[13] Deng Ding-xiong.Shortest Path Query for Road Network Based on SPB Tree[J].Computer Engineering,2011,37(22):56-63
[14] Gargantini I.An Effective Way to Represent Quadtrees[J].Com-munication of ACM,1982,25(12):905-910
[15] Sankaranarayanan J,Alborzi H,Samet H.Efficient query Processing on spatial networks[C]∥GIS’05.2005:200-209
[16] Sankaranarayanan J,Samet H.Distance oracles for spatial network[J].IEEE Computer Society,2009,9:652-663
[17] Sankaranarayanan J,Samet H,Alborzi H.Path oracles for Spatial networks[J].PVLDB,2009,2:1210-1221
[18] Goldberg A V,Harrelson C.Computing the shortest Path:A*search meets graph theory[C]∥ Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.2005:156-165

No related articles found!
Full text



No Suggested Reading articles found!