Network-tree model and shortest path algorithm

	Network-tree model and shortest path algorithm
	Tan, GZ ; Han, XJ ; Gao, W
	2003
发表期刊	COMPUTATIONAL SICENCE - ICCS 2003, PT III, PROCEEDINGS
ISSN	0302-9743
卷号	2659 页码:537-547
摘要	For the first time, this paper proposes the Network-Tree Model (NTM), route optimization theory and wholly new, high performance algorithm for shortest path calculation in large-scale network. We first decompose the network into a set of sub-networks by adopting the idea of multi-hierarchy partition and anomalistic regional partition, and then construct the NTM and the Expanded NTM. The Network-Tree Shortest Path (NTSP) algorithm presented in this paper narrows the searching space of the route optimization within a few sub-networks, so it greatly reduces the requirements for main memory and improves the computational efficiency compared to traditional algorithms. Experiment results based on grid network show that NTSP algorithm achieves much higher computational performance than Dijkstra algorithm and other hierarchical shortest path algorithms.
关键词	nNetwork-tree model shortest path algorithm large-scale network route optimization algorithm
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Interdisciplinary Applications ; Computer Science, Software Engineering ; Computer Science, Theory & Methods
WOS记录号	WOS:000184831900053
出版者	SPRINGER-VERLAG BERLIN
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/13611
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, GZ
作者单位	1.Dalian Univ Technol, Dept Comp Sci & Engn, Dalian 116024, Peoples R China 2.Chinese Acad Sci, Comp Technol Inst, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Tan, GZ,Han, XJ,Gao, W. Network-tree model and shortest path algorithm[J]. COMPUTATIONAL SICENCE - ICCS 2003, PT III, PROCEEDINGS,2003,2659:537-547.
APA	Tan, GZ,Han, XJ,&Gao, W.(2003).Network-tree model and shortest path algorithm.COMPUTATIONAL SICENCE - ICCS 2003, PT III, PROCEEDINGS,2659,537-547.
MLA	Tan, GZ,et al."Network-tree model and shortest path algorithm".COMPUTATIONAL SICENCE - ICCS 2003, PT III, PROCEEDINGS 2659(2003):537-547.