Application of Shortest-Path Algorithm in Embedded GIS System

Abstract:

The shortest-path is an important issue in GIS network analysis, and its implementation in embedded systems has already been used widely in the mobile-device-based GPS navigation and city emergency response system fields. Based on our analysis and verification of the Dijkstra algorithm’s application to road network analysis, we presented in detail the design and program implementation of the Dijkstra algorithm and its flow chart. In this paper, the shortest-path example based on Dijkstra algorithm，which was developed in the MapXmobile5.0 and EVC4.0 environment, has been applied to embedded GIS system successfully. The comparison between the results from the program and manually obtained results has shown the Dijkstra algorithm’s feasibility and accuracy.

• Periodical: Advanced Materials Research (Volume 663)
• Pages: 626-631
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.663.626
• Online since: February 2013
• Authors: Hong Xia Sun, Zheng Zhang
• Keywords: Embedded GIS System, Mobile Device, Shortest-Path

References

[1] Xinyuan Huang, Introduction to Geographic Information System (3rd Edition), Beijing, Higher Education Pressing, (1999).

[2] Jinghai Xu, Qingquan Li, Nianbo Zheng, Mingfeng Li, Embedded-Navigation-Sytem-Oriented GIS-T Road Network Model[J], Mineral University of China Journal, 2008, 37(4)：488-493.

[3] Yuxi Zhu, Ruchun Cui, Junyi Huang, GPS shortest path, searching algorithms and implementation. Computer Engineering and Design. 2005, 26(9)：2437-2442.

[4] Peiming Bao, Dijkstra Algorithm in Distance-based Shortest path searching, Computer Research and Development, . 2001, 38(3)：307-311.

[5] Yuanchen Li, Weiqun Liu, The network shortest path analysis based on Dijkstra algorithm, Microcomputer Application, 2004, 25(3): 295-298.

[6] Feng Wang, Zhisheng You, Chunli Man, Dijkstra algorithm and the N shortest paths application in intelligent transportation system, Computer Application Research, 2006, 23(9): 203-208.

[7] Kaiyi Wang, Chunjiang Zhao, A highly efficient implementation of GIS field shortest path searching problem. Chinese Image and Graphics Journal, 2003, 8(8): 951-956.

[8] Huifeng Ji, Aigong Xu, Da Sui, The design and implementation of Dijkstra algorithm. Liaoning Engineering Technological University Journal， 2008, 27: 222-223.

[9] Dijkstra E.W., A note on two problems in connexion with graphs[J], Numerische Mathematik, 1959, 1. 1: 269-271.

DOI: 10.1007/bf01386390

[10] Cormen T.H., Leiserson C.E., Rivest R.L., and Stein C., Introduction to Algorithms, Second Edition[M], MIT Press and McGraw-Hill, (2001).