点击次数：

论文类型：会议论文

发表时间：2003-06-02

收录刊物：EI

卷号：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. © Springer-Verlag Berlin Heidelberg 2003.