Massive Figure Of The Shortest Path Coding Research

Finding the shortest path (SP) between an arbitrary vertex pair is significant when exploring properties of networks. With the increase of the network size, it becomes an urgent problem to answer shortest path query in real time in network management system. A common way to achieve this is to pre-compute all possible shortest paths and organize them as suitable index structure, so that we can answer shortest path query (SPQ) in constant time. However, the size of the such index will be a great challenge to the capacity of storage, since the number of SPs required to be stored is O(N2).In this paper, we presented our interval-based shortest path index built upon the well-known first-hop partitions, aiming to compress the space cost. We showed the NP-hardness of optimizing the size of the proposed index. In order to get a considerable index size, we presented6methods to get suboptimal numbering function (NF) which reduces the number of the intervals of the FH partitions by renumbering the vertices. By their core method which computes the NFs, these methods fall into two categories:TSP and Region Tree. By the numbers of the NFs, the methods can be classified as single NF methods and multi NFs methods. By the frameworks adopted by the methods, they can be regarded as either standalone method or integrated method which typically integrates with TEDI. In addition, we proposed the First-hop Bipartite, a tool that helps to analyze the distance between two first-hop partitions, based on which we presented a2-opt algorithm to efficiently compute the distances.Experimental results on synthetic networks and real networks show that we successfully reduce the index size and ensure to answer the shortest queries in constant time, without consuming more time to build the compacted index structure.