Title :
An Algorithm of Shortest Path Based on Dijkstra for Huge Data
Author :
Fuhao, Zhang ; Jiping, Liu
Author_Institution :
Res. Center of Gov. Geographic Inf. Syst., Chinese Acad. of Surveying & Mapping, Beijing, China
Abstract :
This paper introduces the classical Dijkstra algorithm in detail, and illustrates the method of implementation of the algorithm and the disadvantages of the algorithm: the network nodes require square-class memory, so it is difficult to quantify the shortest path of the major nodes. At the same time, it describes the adjacent node algorithm which is an optimization algorithm based on Dijkstra algorithm. The algorithm makes full use of connection relation of arcs in the network topology information, and avoids the use of correlation matrix that contains substantial infinite value, making it more suitable analysis of the network for mass data. It is proved that the algorithm can save a lot of memory and is more suitable to the network with huge nodes.
Keywords :
data analysis; geographic information systems; matrix algebra; optimisation; GIS; adjacent node algorithm; classical Dijkstra algorithm; correlation matrix; geographic information system; mass data analysis; network nodes; optimization algorithm; square-class memory; Algorithm design and analysis; Costs; Data analysis; Equations; Fuzzy systems; Geographic Information Systems; Government; Information analysis; Information science; Network topology; Dijkstra; GIS; Network; Network analysis; Shortest path analysis;
Conference_Titel :
Fuzzy Systems and Knowledge Discovery, 2009. FSKD '09. Sixth International Conference on
Conference_Location :
Tianjin
Print_ISBN :
978-0-7695-3735-1
DOI :
10.1109/FSKD.2009.848