Parallel algorithms for the single source shortest path problem

We present several parallel algorithms for the problem of finding shortest paths from a specified vertex (called the source) to all others in a weighted directed graph. The algorithms are for machines ranging from array processors, multipleinstruction multiple-data stream machines to a special network of processors. These algorithms have been designed by “parallelizing” two classic sequential algorithms — one due to Dijkstra (1959), the other due to Moore (1957). Our interest is not only in obtaining speeded-up parallel versions of the algorithms but also in exploring the design principles, the commonality of correctness proofs of the different versions, and the subjective complexity of explaining and understanding these versions.     

ADA multitasking and the single source shortest path problem

This paper examines the implementation in ADA of several parallel algorithms for solving the single source shortest path problem. The algorithm favor certain parallel architectures: vector machine, tree machine, and a distributed processor environment. The paper gives ADA implementations of the algorithms that attempt to retain the preferential treatment to the particular hardware, and discusses whether with proper translation, preferential efficiency can be maintained.     

SPLZ: An efficient algorithm for single source shortest path problem using compression method

Efficient solution of the single source shortest path (SSSP) problem on road networks is an important requirement for numerous real-world applications. This paper introduces an algorithm for the SSSP problem using compression method. Owning to precomputing and storing all-pairs shortest path (APSP), the process of solving SSSP problem is a simple lookup of a little data from precomputed APSP and decompression. APSP without compression needs at least 1TB memory for a road network with one million vertices. Our algorithm can compress such an APSP into several GB, and ensure a good performance of decompression. In our experiment on a dataset about Northwest USA (with 1.2 millions vertices), our method can achieve about three orders of magnitude faster than Dijkstra algorithm based on binary heap.     

Comparing evolutionary algorithms to the (1+1) -EA

In this paper, we study the conditions in which the random hill-climbing algorithm (1 + 1)-EA compares favorably to other evolutionary algorithms (EAs) in terms of fitness function distribution at a given iteration and with respect to the average optimization time. Our approach is applicable when the reproduction operator of an evolutionary algorithm is dominated by the mutation operator of the (1 + 1)-EA. In this case one can extend the lower bounds obtained for the expected optimization time of the (1 + 1)-EA to other EAs based on the dominated reproduction operator. This method is demonstrated on the sorting problem with HAM landscape and the exchange mutation operator. We consider several simple examples where the (1 + 1)-EA is the best possible search strategy in the class of the EAs.     

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.     

最短路径问题的禁忌搜索求解方法

针对网络优化算法中的最短路径（Shortest Path,SP）问题,建立了有约束条件的SP问题模型,并探讨了使用禁忌搜索（Tabu Search,TS）算法对其求解的算法框架及关键步骤。该求解方法寻优能力强,结构简明,能方便处理问题约束,具有智能计算方法的优点。最后,通过实例进行测试和比较,证明算法收敛速度快,并能够获得满足约束条件的优解集合,能适应较差网络条件下的多条路径选择,算法是可行和有效的。     

Rapid Physarum Algorithm for shortest path problem

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time.     

MapReduce求解物流配送单源最短路径研究

针对物流配送路线优化,提出了将配送路线问题分解成若干可并行操作的子问题的云计算模式。详细论述了基于标色法的MapReduce广度优先算法并行化模型、节点数据结构、算法流程和伪代码程序,并通过将该算法应用于快递公司的实际配送,验证了该算法的可行性。     

Analysis of FPTASes for the multi-objective shortest path problem

We propose a new FPTAS for the multi-objective shortest path problem with non-negative and integer arc costs. The algorithm uses elements from both an exact labeling algorithm and an FPTAS proposed by Tsaggouris and Zaroliagis [25]. We analyze the running times of these three algorithms both from a theoretical and a computational point of view. Theoretically, we show that there are instances for which the new FPTAS runs arbitrarily faster than the other two algorithms. Furthermore, for the bi-objective case, the number of approximate solutions generated by the proposed FPTAS is at most the number of Pareto-optimal points multiplied by the number of nodes. By performing a set of computational tests, we show that the new FPTAS performs best in terms of running time in case there are many dominated paths and the number of Pareto-optimal points is not too small.     

一种快速求解最短路径巡游问题的涟漪扩散算法

针对最短路径巡游问题（SPTP）,提出了基于涟漪扩散算法（RSA）特征的SPTP分解方法。RSA通过模拟水面上涟漪传播的现象,在SPTP子问题间建立联系,相较于其他基于问题分解的算法减少了计算冗余度。进一步改进RSA,使其在维持时间复杂度不变的情况下求解多起点—多终点SPTP。在多种拓扑结构的网络中进行对比实验,结果表明,RSA在保证最优性的同时运算效率最高。RSA对于多起点—多终点SPTP的高效求解,可为多种现实问题快速提供解决方案,具有很高的应用价值。     

求解最短路径的遗传算法中若干问题的讨论

针对道路交通网络中的最短路径问题,讨论了遗传算法中遗传算子的设计及运行参数的选择,提出一种新的交叉算子,提高了种群多样性.通过计算机仿真实验,比较了多种遗传算子设计方案的优劣及不同运行参数对算法效果的影响,为实际应用提供了参考.采用VC语言实现该遗传算法,并应用于实际的电子地图中,结果表明了算法的有效性和实用性.     

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), where Δ is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.     

On an exact method for the constrained shortest path problem

The constrained shortest path (CSP) is a well known NP-Hard problem. Besides from its straightforward application as a network problem, the CSP is also used as a building block under column-generation solution methods for crew scheduling and crew rostering problems. We propose an exact solution method for the CSP capable of handling large-scale networks in a reasonable amount of time. We compared our approach with three different state-of-the-art algorithms for the CSP and found optimal solutions on networks with up to 40,000 nodes and 800,000 arcs. We extended the algorithm to effectively solve the auxiliary problems of a multi-activity shift scheduling problem and a bus rapid transit route design problem tackled with column generation. We obtained significant speedups against alternative column generation schemes that solve the auxiliary problem with state-of-the-art commercial (linear) optimizers. We also present a first parallel version of our algorithm that shows promising results.     

A systolic array algorithm for the algebraic path problem (shortest paths; Matrix inversion)

It is shown how the Gauß-Jordan Elimination algorithm for the Algebraic Path Problem can be implemented on a hexagonal systolic array of a quadratic number of simple processors in linear time. Special instances of this general algorithm include parallelizations of the Warshall-Floyd Algorithm, which computes the shortest distances in a graph or the transitive closure of a relation, and of the Gauß-Jordan Elimination algorithm for computing the inverse of a real matrix.     

必经点约束型最短路径问题的研究

为了解决网络路由中带有必经点约束的网络拓扑中最优路径的问题,提出了采用改进的蚁群算法和Dijkstra算法对最优路径进行规划。首先,针对含有必经点约束的问题,在信息素初始化时增加在必经点上的信息素。其次,为了能够更好地找到最优解,采用了狼群分配算法进行信息素更新,提高了收敛速度,并且采用了Dijkstra算法对蚂蚁找到的最优路径进行二次优化。最后,分别用不同节点和必经点规模的网络进行实验,并与基本的蚁群算法进行了比较,证明了改进蚁群算法的正确性和高效性。     

An ant colony optimization algorithm for the bi-objective shortest path problem

Multi-objective shortest path problem (MOSP) is an extension of a traditional single objective shortest path problem that seeks for the efficient paths satisfying several conflicting objectives between two nodes of a network. MOSP is one of the most important problems in network optimization with wide applications in telecommunication industries, transportation and project management. This research presents an algorithm based on multi-objective ant colony optimization (ACO) to solve the bi-objective shortest path problem. To analyze the efficiency of the algorithm and check for the quality of solutions, experimental analyses are conducted. Two sets of small and large sized problems that generated randomly are solved. Results on the set problems are compared with those of label correcting solutions that is the most known efficient algorithm for solving MOSP. To compare the Pareto optimal frontiers produced by the suggested ACO algorithm and the label correcting algorithm, some performance measures are employed that consider and compare the distance, uniformity distribution and extension of the Pareto frontiers. The results on the set of instance problems show that the suggested algorithm produces good quality non-dominated solutions and time saving in computation of large-scale bi-objective shortest path problems.     

An enhanced exact procedure for the absolute robust shortest path problem

The aim of this paper is to investigate the use of heuristic information to efficiently solve to optimality the robust shortest path problem. Starting from the exact algorithm proposed by Murty and Her, we describe how this algorithm can be enhanced by using heuristic rules and evaluation functions to guide the search. The efficiency of the proposed enhanced approach is tested over a range of random generated instances. Our computational results indicate that the use of heuristic criteria is able to speed up considerably the search and that the enhanced exact solution method outperforms the state‐of‐the‐art algorithm proposed by Murty and Her in most of the instances.     

Fuzzy Dijkstra algorithm for shortest path problem under uncertain environment

A common algorithm to solve the shortest path problem (SPP) is the Dijkstra algorithm. In this paper, a generalized Dijkstra algorithm is proposed to handle SPP in an uncertain environment. Two key issues need to be addressed in SPP with fuzzy parameters. One is how to determine the addition of two edges. The other is how to compare the distance between two different paths with their edge lengths represented by fuzzy numbers. To solve these problems, the graded mean integration representation of fuzzy numbers is adopted to improve the classical Dijkstra algorithm. A numerical example of a transportation network is used to illustrate the efficiency of the proposed method.