An optimized Dijkstra algorithm for Embedded-GIS

Author

Zhang, Dong ; Wei, ZuKuan ; Kim, Jae-Hong ; Tang, Shuguang

Author_Institution

Sch. of Comput. Sci. & Eng., Univ. of Electron. Sci. & Technol. of China, Chengdu, China

Volume

1

fYear

2010

fDate

25-27 June 2010

Abstract

The embedded-GIS system´s architecture and characteristics are researched and analyzed. The limitation of Dijkstra algorithms for Embedded-GIS is given. A new algorithm of shortest path analysis-“ optimized Dijkstra algorithm for Embedded-GIS” is given. This method implement a new graphic storage structure and a new finding technique. The needed memory of this algorithm is decreased, and the searching speed of this algorithm is also improved. An element-“X[Vi,Vj]” is presented for shortest path analysis in this algorithm. Finally the experiment based on Embedded-GIS indicated this algorithm´s efficiency and practicality.

Keywords

embedded systems; geographic information systems; embedded-GIS; finding technique; graphic storage structure; optimized Dijkstra algorithm; shortest path analysis; Algorithm design and analysis; Computer science; Design engineering; Embedded computing; Embedded system; Geographic Information Systems; Hardware; Industrial electronics; Navigation; Operating systems; Embedded-GIS; dijkstra algorithms; shortest path analysis;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Design and Applications (ICCDA), 2010 International Conference on

Conference_Location

Qinhuangdao

Print_ISBN

978-1-4244-7164-5

Electronic_ISBN

978-1-4244-7164-5

Type

conf

DOI

10.1109/ICCDA.2010.5541160

Filename

5541160