Abstract:With the increasing of data in complex networks, the efficiency of classic algorithms such as Dijkstra algorithm is very low. To solve this problem, the researchers put forward a number of approximate search algorithms, but how to reduce the computational complexity and also keep the accuracy has been a big difficulty. According to the structural characteristics of complex networks, this article introduces regional division, improves the structure of the tree decomposition, and constructs graph into a tree to search the target vertex, getting a new the shortest path approximate algorithm for complex networks. In addition, the proposed algorithm not only reduces the computational complexity but also remains the high accuracy of approximation by examples.