基于规则的最短路径查询算法

最短路径查询是图数据管理中非常重要的一类问题.研究了基于规则的最短路径查询,它是一类特殊的最短路径查询问题.给定起点和终点,基于规则的最短路径查询是指找到一条从起点到终点的最短路径,使得此路径经过用户指定点集中的所有点,并且某些点的访问顺序满足一定的偏序规则.该问题被证明是一个NP-hard问题.目前已有的工作侧重于空间数据集（两点之间的最短距离用欧氏距离表示）上基于规则的最短路径问题,它采用穷举的方式列出所有满足规则的路径,然后选择长度最小的路径作为问题的解.然而在实际的道路交通网中,两点之间的距离等于两点之间的最短路径的长度,它往往大于两点之间的欧氏距离;此外,采用穷举的方式会造成大量重复的计算.因此,设计了一种前向搜索算法以及一些优化技术来求解该问题.最后,在不同的真实数据集上设计了大量的实验来验证算法的有效性.实验结果表明,该算法可以快速给出问题的解,而且算法的效率在很大程度上超过了现有的算法.     

Estimating graph distance and centrality on shared nothing architectures

We present a parallel toolkit for pairwise distance computation in massive networks. Computing the exact shortest paths between a large number of vertices is a costly operation, and serial algorithms are not practical for billion‐scale graphs. We first describe an efficient parallel method to solve the single source shortest path problem on commodity hardware with no shared memory. Using it as a building block, we introduce a new parallel algorithm to estimate the shortest paths between arbitrary pairs of vertices. Our method exploits data locality, produces highly accurate results, and allows batch computation of shortest paths with 7% average error in graphs that contain billions of edges. The proposed algorithm is up to two orders of magnitude faster than previously suggested algorithms and does not require large amounts of memory or expensive high‐end servers. We further leverage this method to estimate the closeness and betweenness centrality metrics, which involve systems challenges dealing with indexing, joining, and comparing large datasets efficiently. In one experiment, we mined a real‐world Web graph with 700 million nodes and 12 billion edges to identify the most central vertices and calculated more than 63 billion shortest paths in 6 h on a 20‐node commodity cluster. Copyright © 2014 John Wiley & Sons, Ltd.     

基于Floyd算法的多重最短路问题的改进算法

路径分析是网络分析最基本的问题,其核心是对最短路径的求解。Floyd算法是一种求取最短路的经典算法。分析发现,两点间可能存在多条权重相同的最短路径,而这一点Floyd算法没有涉及。以无向联通图为研究对象,设计了基于Floyd求解多重等价最短路算法,并分析计算了一个实际算例。计算结果表明,基于Floyd的多重等价最短路算法可以有效解决多重等价最短路问题。     

An efficient path computation model for hierarchically structured topographical road maps

In this paper, we have developed a HiTi (Hierarchical MulTi) graph model for structuring large topographical road maps to speed up the minimum cost route computation. The HiTi graph model provides a novel approach to abstracting and structuring a topographical road map in a hierarchical fashion. We propose a new shortest path algorithm named SPAH, which utilizes HiTi graph model of a topographical road map for its computation. We give the proof for the optimality of SPAH. Our performance analysis of SPAH on grid graphs showed that it significantly reduces the search space over existing methods. We also present an in-depth experimental analysis of HiTi graph method by comparing it with other similar works on grid graphs. Within the HiTi graph framework, we also propose a parallel shortest path algorithm named ISPAH. Experimental results show that inter query shortest path problem provides more opportunity for scalable parallelism than the intra query shortest path problem.     

Isometric-path numbers of block graphs

An isometric path between two vertices in a graph G is a shortest path joining them. The isometric-path number of G, denoted by ip(G), is the minimum number of isometric paths required to cover all vertices of G. In this paper, we determine exact values of isometric-path numbers of block graphs. We also give a linear-time algorithm for finding the corresponding paths.     

Fast approximation of betweenness centrality through sampling

Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices (or edges) in a network in terms of the fraction of shortest paths that pass through them. Since exact computation in large networks is prohibitively expensive, we present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices (or edges): all approximate values are within an additive factor \(\varepsilon \in (0,1)\) from the real values, with probability at least \(1-\delta \). The second algorithm focuses on the top-K vertices (or edges) with highest betweenness and estimate their betweenness value to within a multiplicative factor \(\varepsilon \), with probability at least \(1-\delta \). This is the first algorithm that can compute such approximation for the top-K vertices (or edges). By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we can bound the sample size needed to achieve the desired approximations. We obtain sample sizes that are independent from the number of vertices in the network and only depend on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any quantitative property of the graph. An extensive experimental evaluation on real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices grows than other algorithms with similar approximation guarantees.     

Dynamic algorithms for the shortest path routing problem: learning automata-based solutions.

This paper presents the first Learning Automaton-based solution to the dynamic single source shortest path problem. It involves finding the shortest path in a single-source stochastic graph topology where there are continuous probabilistic updates in the edge-weights. The algorithm is significantly more efficient than the existing solutions, and can be used to find the "statistical" shortest path tree in the "average" graph topology. It converges to this solution irrespective of whether there are new changes in edge-weights taking place or not. In such random settings, the proposed learning automata solution converges to the set of shortest paths. On the other hand, the existing algorithms will fail to exhibit such a behavior, and would recalculate the affected shortest paths after each weight-change. The important contribution of the proposed algorithm is that all the edges in a stochastic graph are not probed, and even if they are, they are not all probed equally often. Indeed, the algorithm attempts to almost always probe only those edges that will be included in the shortest path graph, while probing the other edges minimally. This increases the performance of the proposed algorithm. All the algorithms were tested in environments where edge-weights change stochastically, and where the graph topologies undergo multiple simultaneous edge-weight updates. Its superiority in terms of the average number of processed nodes, scanned edges and the time per update operation, when compared with the existing algorithms, was experimentally established. The algorithm can be applicable in domains ranging from ground transportation to aerospace, from civilian applications to military, from spatial database applications to telecommunications networking.     

PHAST: Hardware-accelerated shortest path trees

We present a novel algorithm to solve the non-negative single-source shortest path problem on road networks and graphs with low highway dimension. After a quick preprocessing phase, we can compute all distances from a given source in the graph with essentially a linear sweep over all vertices. Because this sweep is independent of the source, we are able to reorder vertices in advance to exploit locality. Moreover, our algorithm takes advantage of features of modern CPU architectures, such as SSE and multiple cores. Compared to Dijkstra’s algorithm, our method needs fewer operations, has better locality, and is better able to exploit parallelism at multi-core and instruction levels. We gain additional speedup when implementing our algorithm on a GPU, where it is up to three orders of magnitude faster than Dijkstra’s algorithm on a high-end CPU. This makes applications based on all-pairs shortest-paths practical for continental-sized road networks. Several algorithms, such as computing the graph diameter, arc flags, or exact reaches, can be greatly accelerated by our method.     

图聚类的算法及其在社会关系网络中的应用

研究图聚类的算法问题。在基于划分的图聚类中,重点比较点与点之间距离的计算方法及其对聚类结果的影响。由于社会关系网络图中点没有坐标值,所以不能使用欧几里得距离和曼哈坦距离。使用k-medoids聚类算法时,分别采用最短距离和随机漫步距离算法,将DBLP数据集构成的社会关系网络图分类成各个子图,通过实验数据验证两种算法的优劣。实验证明最短距离算法获得聚类效果更为理想,达到了较好的分类效果。     

参考节点嵌入最短距离估算在图聚类中的应用

为解决社会关系网络图中节点没有坐标值、不能采用传统的欧几里得距离和曼哈坦距离进行聚类的问题,提出采用最短路径算法,来衡量点与点之间的相异度.针对最短路径算法具有时间复杂度大的缺点,引入基于参考节点嵌入的最短距离估算思想来估算两点之间的近似距离.在此基础上,针对DBLP数据集构成的社会关系网络图进行聚类,使用基于划分的k-medoids算法,分别采用以上两种距离算法,比较其优劣.实验证明改进后的算法和最短路径算法中的Dijkstra 算法相比,距离误差率小,时间复杂度大大降低,在提高效率的同时,取得了同样好的聚类效果.     

The exact distance to destination in undirected world

Shortest distance queries are essential not only in graph analysis and graph mining tasks but also in database applications, when a large graph needs to be dealt with. Such shortest distance queries are frequently issued by end-users or requested as a subroutine in real applications. For intensive queries on large graphs, it is impractical to compute shortest distances on-line from scratch, and impractical to materialize all-pairs shortest distances. In the literature, 2-hop distance labeling is proposed to index the all-pairs shortest distances. It assigns distance labels to vertices in a large graph in a pre-computing step off-line and then answers shortest distance queries on-line by making use of such distance labels, which avoids exhaustively traversing the large graph when answering queries. However, the existing algorithms to generate 2-hop distance labels are not scalable to large graphs. Finding an optimal 2-hop distance labeling is NP-hard, and heuristic algorithms may generate large size distance labels while still needing to pre-compute all-pairs shortest paths. In this paper, we propose a multi-hop distance labeling approach, which generates a subset of the 2-hop distance labels as index off-line. We can compute the multi-hop distance labels efficiently by avoiding pre-computing all-pairs shortest paths. In addition, our multi-hop distance labeling is small in size to be stored. To answer a shortest distance query between two vertices, we first generate the query-specific small set of 2-hop distance labels for the two vertices based on our multi-hop distance labels stored and compute the shortest distance between the two vertices based on the 2-hop distance labels generated on-line. We conducted extensive performance studies on large real graphs and confirmed the efficiency of our multi-hop distance labeling scheme.     

不可达顶点剪枝算法及其在最短路径中的应用

[k]步可达性查询用于回答图[G]中从顶点[u]到达顶点[v]最多[k]步是否存在路径,但其多用于无权图的可达性研究。针对加权图,在图中构建了最早到达、逆向最早到达和最晚到达等三个索引,并应用这三个索引实现对不可达顶点的快速剪枝,从而有效地缩减了加权图的规模。运用该方法建立索引并剪枝顶点的时间复杂度与空间复杂度分别为[O(n+e)]和[O(n)],这里[n]和[e]分别为图中顶点的数目和边的数目。该方法可以与Dijkstra算法、Floyd算法和A*算法等多种传统算法相结合,并应用于最短路径求解,从而提高传统算法计算性能。最后以物流配送网络为例进行了实验验证,实验结果表明提出的方法可以正确并高效地对不必要计算的顶点进行剪枝,从而加快了最短路径求解速度,验证了提出方法的有效性。     

Refreshment of the shortest path cache with change of single edge

The problem of caching shortest paths has been widely studied. All of existing methods that address this problem assume that the condition of road networks does not change with time. In this paper, we study how to refresh a cache when one edge of the underlying road network (graph) changes. A bitmap-based cache structure is proposed to store and give access to shortest paths. In the following, algorithms are developed to detect shortest paths that are affected by the change of edge. After detecting affected paths, several heuristic-based refreshment strategies are proposed to update the cache. We have conducted a series of experiments to compare the performance of proposed strategies. It shows that replacing affected shortest paths with new paths whose benefit values are the largest should be applied in the shortest path caching applications such as navigation and map services.     

Two-level heaps: a new priority queue structure with applications to the single source shortest path problem

The single source shortest paths problem with positive edge weights (SSSPP) is one of the more widely studied problems in operations research and theoretical computer science, on account of its wide applicability to practical situations. This problem was first solved in polynomial time by Dijkstra, who showed that by extracting vertices with the smallest distance from the source and relaxing its outgoing edges, the shortest path to each vertex is obtained. Variations of this general theme have led to a number of algorithms which work well in practice. At the heart of a Dijkstra implementation is the technique used to implement a priority queue. It is well known that using Dijkstra’s approach requires Ω(n log n) steps on a graph having n vertices, since it essentially sorts vertices based on their distances from the source. Accordingly, the fastest implementation of Dijkstra’s algorithm on a graph with n vertices and m edges should take Ω(m + n · log n) time, and consequently, the Dijkstra procedure for SSSPP using Fibonacci Heaps is optimal in the comparison-based model. In this paper, we introduce a new data structure to implement priority queues called two-level heap (TLH) and a new variant of Dijkstra’s algorithm called Phased Dijkstra. We contrast the performance of Dijkstra’s algorithm (both the simple and the phased variants) using a number of data structures to implement the priority queue and empirically establish that TLH are far superior to Fibonacci heaps on every graph family considered. It is to be noted that our profiling includes both sparse and dense graphs.     

A new formulation and approach for the black and white traveling salesman problem

This paper proposes a new formulation and a column generation approach for the black and white traveling salesman problem. This problem is an extension of the traveling salesman problem in which the vertex set is divided into black vertices and white vertices. The number of white vertices visited and the length of the path between two consecutive black vertices are constrained. The objective of this problem is to find the shortest Hamiltonian cycle that covers all vertices satisfying the cardinality and the length constraints. We present a new formulation for the undirected version of this problem, which is amenable to the Dantzig–Wolfe decomposition. The decomposed problem which is defined on a multigraph becomes the traveling salesman problem with an extra constraint set in which the variable set is the feasible paths between pairs of black vertices. In this paper, a column generation algorithm is designed to solve the linear programming relaxation of this problem. The resulting pricing subproblem is an elementary shortest path problem with resource constraints, and we employ acceleration strategies to solve this subproblem effectively. The linear programming relaxation bound is strengthened by a cutting plane procedure, and then column generation is embedded within a branch-and-bound algorithm to compute optimal integer solutions. The proposed algorithm is used to solve randomly generated instances with up to 80 vertices.     

Pierce point minimization and optimal torch path determination in flame cutting

This paper addresses the problem of sequencing a torch for the cutting of a stock sheet nested with regular or irregular parts. The image of the nesting is reduced to an equivalent graph, and the objective is to traverse this graph with a minimum number of pierce points, or blowthroughs. If the graph has $\text{2k}$ vertices of odd degree, then $\text{k}$ pierce points are necessary and sufficient to traverse the graph. The torch path problem formulation includes manufacturing cost, efficiency, and distortion considerations. We present three algorithms for the problem. The first algorithm shows how to determine the $\text{k}$ torch paths, and is optimal in run time complexity. The second algorithm uses trim margin edges to investigate further reduction in the number of pierce points. The third algorithm guarantees that for the special case where a torch path has no vertices of odd degree, no piece will be dropped that needs further interior cuts. Some possible extensions to this work are also addressed.     

An efficient Dijkstra-like labeling method for computing shortest odd/even paths

We show how the problem of determining shortest paths of even or odd length between two specified vertices in a graph G = (V, E) can be reduced to the problem of finding a shortest alternating path with respect to a specific matching in a related graph H. This problem can be solved by a Dijkstra-like labeling procedure of complexity O(|V|²) respectively O(|E|log|V|). Interpreting this procedure appropriately the method can then be applied directly on the given graph G.     

Complexity results on labeled shortest path problems from wireless routing metrics

Metrics to assess the cost of paths through networks are critical to ensuring the efficiency of network routing. This is particularly true in multi-radio multi-hop wireless networks. Effective metrics for these networks must measure the cost of a wireless path based not only on traditional measures such as throughput, but also on the distribution of wireless channels used. In this paper, we argue that routing metrics over such networks may be viewed as a class of existing shortest path problems, the formal language constrained path problems.On this basis, we describe labeled path problems corresponding to two multi-radio wireless routing metrics: Weighted Cumulative Expected Transmission Time (WCETT), developed by Draves et al., and Metric for Interference and Channel-switch (MIC), developed by Yang et al. For the first, we give a concise proof that calculating shortest WCETT paths is strongly NP-Complete for a variety of graph classes. We also show that the existing heuristic given by Draves et al. is an approximator. For the second, we show that calculating loop-free (simple) shortest MIC paths is NP-Complete, and additionally show that the optimization version of the problem is NPO PB-Complete. This result implies that shortest simple MIC paths are only poorly approximable in the worst case.Furthermore, we demonstrate how the polynomial-time algorithm for shortest MIC paths is derivable from an existing language constrained shortest path algorithm. We use this as a basis to exhibit the general utility of viewing multi-channel wireless routing metrics as labeled graph problems, and discuss how a class of related polynomial-time computable metrics are derivable from this algorithm.     

Stability routing with constrained path length for improved routability in dynamic MANETs

Quality of service (QoS) routing is known to be an NP-hard problem in case of two or more additive constraints, and several exact algorithms and heuristics have been proposed to address this issue. In this paper, we consider a particular two-constrained quality of service routing problem maximizing path stability with a limited path length in the quest of improving routability in dynamic multi-hop mobile wireless ad hoc networks. First, we propose a novel exact algorithm to solve the optimal weight-constrained path problem. We instantiate our algorithm to solve the most stable path not exceeding a certain number of hops, in polynomial time. This algorithm is then applied to the practical case of proactive routing in dynamic multi-hop wireless ad hoc networks. In these networks, an adequate compromise between route stability and its length in hops is essential for appropriately mitigating the impact of the network dynamics on the validity of established routes. Secondly, we set up a common framework for the comparison between three families of proactive routing: the shortest path-based routing, the most stable path-based routing and our proposed most stable constrained path routing. We show then through extensive simulations that routing based on our proposed algorithm selects appropriate stable paths yielding a very high routability with an average path length just above that of the shortest paths.     

Time-Efficient Maze Routing Algorithms on Reconfigurable Mesh Architectures

The routing problem is one of the most widely studied problems in VLSI design. Maze-routing algorithms are used in VLSI routing and robot path planning. Efficiency of the parallel maze routing algorithms which were mostly based on C. Y. Lee's algorithm8is poor. In this paper, we propose time-efficient algorithms to solve the maze-routing problem on a reconfigurable mesh architecture. The constant-time algorithms presented include: (i) testing the existence of specific types of paths between two terminals, and (ii) finding an absolute shortest path (ASP) and a shortest duplex-path (SDP). In addition, a fast algorithm to find the single shortest path (SSP) is presented. The simulation results indicate that a large percentage of the shortest paths that exist between two randomly selected terminals fall into one of the categories studied in this paper.