BFS For Solving Shortest Path Based On Path Blocking

In recent years, with the birth and rise of the network, network disciplines have been widely applied to more other disciplines, such as physics, chemistry,biology, politics, economy, Internet, engineering development and social life.With the advent of large data, the scale of complex networks based on the extraction and abstraction of each discipline will become ever greater. The optimal path problem based on the shortest path has always been widely applied to computer science, traffic science, engineering science, control science, traffic engineering and geographic information science. It is also the basis of many problems and research hot spots, such as design routes,allocation of resources and so on. As the amount of data processed by computers continues to increase and become larger, the time of many classical algorithms are getting longer and longer. For example, Dijkstra algorithm needs O (n ? 2) time complexity, makes the load of computer, and cannot meet the requirement of solving the all-pairs shortest path. Therefore, there is a further and higher time requirement for the performance of the network analysis algorithm - that is to complete the calculation of the all-pair shortest path of the network in a shorter time. Therefore, BFS algorithm based on path blocking is proposed in the background of such subject.The main work of this paper is as follows,1. This topic is based on the classic network traversal algorithm BFS(Breadth First Search), introducing the path blocking strategy. The BFS algorithm (block algorithm) based on path blocking is obtained, and the whole process of the block algorithm is expounded in detail.2. Based on the analysis of the block algorithm, the selection of the blocking points is made to solve the single-source shortest path node ordering and so on. The results show that we get some algorithms which are better than BFS algorithm and block algorithm, and spend less time than BFS algorithm and block algorithm.(1) The first blocking strategy is to sort the nodes solving the single source shortest path in descending order of the node's degree. This strategy firstly be used to solve some of the key nodes in large-scale complex networks(the shortest path problem is reflected in the larger value of the node), can make the algorithm in the subsequent processing,and can make the blocking effect better. On the basis of the block algorithm, the blockODD (block of descendant degree) algorithm is obtained by introducing this strategy.(2) The second blocking strategy is to limit the number of blocking .In the block algorithm processing based on the experiment, block the number of times and block algorithm processing time showing a similar trend, in order to further reduce the processing time of the block algorithm ,we make a comparison of the threshold and a real-time statistics into the number of nodes to be traversed queue to further make the choice of blocking points more stringent, making the efficiency of the algorithm further improve. On the basis of the block algorithm, by introducing this strategy, we get the enqueue-block algorithm cluster.(3) The third blocking strategy is based on the shortest path formed by the spanning tree as a theoretical basis. By analyzing the structure of the network,we can conclude that the blocking effect of the neighbor node of the starting node is better, and after one block, the single-source shortest path of the starting node has a high correct rate, especially the node with the value of 1 through the neighbor node, the blocking effect is the best, the correct rate is the highest. On the basis of the block algorithm, the first-level-block algorithm is obtained by introducing this strategy.Based on the block algorithm, we compare solving time of APSP and SSSP by using several algorithms. In the experiment, several algorithms are obtained faster than the BFS algorithm.