A Practical Parallel Algorithm for All-Pair Shortest Path Based on Pipelining

On the basis of Floyd algorithm with the extended path matrix, a parallel algorithm which resolves all-pair shortest path （APSP） problem on cluster environment is analyzed and designed. Meanwhile, the parallel APSP pipelining algorithm makes full use of overlapping technique between computation and communication. Compared with broadcast operation, the parallel algorithm reduces communication cost. This algorithm has been implemented on MPI on PC-cluster. The theoretical analysis and experimental results show that the parallel algorithm is an efficient and scalable algorithm.

An efficient parallel algorithm for shortest pathsin planar layered digraphs

This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.

The Algorithm of the Time-Dependent Shortest Path Problem with Time Windows

In this paper, we present a new algorithm of the time-dependent shortest path problem with time windows. Give a directed graph , where V is a set of nodes, E is a set of edges with a non-negative transit-time function . For each node , a time window ?within which the node may be visited and ?, is non-negative of the service and leaving time of the node. A source node s, a destination node d and a departure time?t0, the time-dependent shortest path problem with time windows asks to find an s, d-path that leaves a source node s at a departure time t0;and minimizes the total arrival time at a destination node d. This formulation generalizes the classical shortest path problem in which ce are constants. Our algorithm of the time windows gave the generalization of the ALT algorithm and A* algorithm for the classical problem according to Goldberg and Harrelson [1], Dreyfus [2] and Hart et al. [3].

An Investigation on the Effect of Migration Strategy on Parallel GA-Based Shortest Path Routing Algorithm

Genetic algorithm (GA) is one of the alternative approaches for solving the shortest path routing problem. In previous work, we have developed a coarse-grained parallel GA-based shortest path routing algorithm. With parallel GA, there is a GA operator called migration, where a chromosome is taken from one sub-population to replace a chromosome in another sub-population. Which chromosome to be taken and replaced is subjected to the migration strategy used. There are four different migration strategies that can be employed: best replace worst, best replace random, random replace worst, and random replace random. In this paper, we are going to evaluate the effect of different migration strategies on the parallel GA-based routing algorithm that has been developed in the previous work. Theoretically, the migration strategy best replace worst should perform better than the other strategies. However, result from simulation shows that even though the migration strategy best replace worst performs better most of the time, there are situations when one of the other strategies can perform just as well, or sometimes better.

An Evolutionary Algorithm Coupled to an Outranking Method for the Multicriteria Shortest Paths Problem

In this article, we are interested in solving a combinatorial optimization problem, the shortest path problem in a multi-attribute graph, by the out-ranking methods. A multi-attribute graph has simultaneously qualitative and quantitative criteria. This situation gives rise to incomparable paths thus forming the Pareto front. Outranking methods in Multi-criteria Decision Making (MCDM) are the only methods that can take into account this situation (incomparability of actions). After presenting the categories of Multi-criteria Decision Making (MCDM) and the difficulties related to the problems of the shortest paths, we propose an evolutionary algorithm based on the outranking methods to solve the problem of finding “best” paths in a multi-attribute graph with non-additive criteria. Our approach is based on the exploration of induced subgraphs of the outranking graph. Properties have been established to serve as algorithmic basis. Numerical experiments have been carried out and the results presented in this article.

The Shortest Path Analysis Based on Road Network

Rational planning of agricultural product transport route from initial node to destination node can effectively reduce the cost price of agricultural products,and the calculation of shortest path between any two points also affects people’s daily travel.Taking Heze Railway Station to Heze College for example,with remote sensing image data as the base map,we conduct vectorization and topological analysis on roads in the target area.With Dijkstra as theoretical basis of shortest path algorithm,we use ArcG IS network analysis method to build road network,and calculate the planning program of the shortest distance path,the shortest path by driving and the shortest path by walking.

Distribution network planning based on shortest path

In order to form an algorithm for distribution network routing,an automatic routing method of distribution network planning was proposed based on the shortest path.The problem of automatic routing was divided into two steps in the method:the first step was that the shortest paths along streets between substation and load points were found by the basic ant colony algorithm to form a preliminary radial distribution network,and the second step was that the result of the shortest path was used to initialize pheromone concentration and pheromone updating rules to generate globally optimal distribution network.Cases studies show that the proposed method is effective and can meet the planning requirements.It is verified that the proposed method has better solution and utility than planning method based on the ant colony algorithm.

Optimal parallel algorithm for shortest-paths problem on interval graphs

This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.

Using Link Analysis Technique with a Modified Shortest-Path Algorithm to Fight Money Laundering

Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.

A~*算法在Shortest-Path方面的优化研究

在游戏和地理信息系统开发等领域中,专门针对最短路径搜索方面的优化研究较多,尤其是最短路径中启发式搜索算法中的A*算法的效率优化研究.本文将针对在人工智能或算法研究中的使用的地图大多数是基于任意图而不是网格图的状况,通过任意图与网格图及方向的相结合,提出了三种优化A*算法的启发式函数搜索策略,较好地减小了算法搜索的范围和规模,有效地提高了A*算法的运行效率.最后的实验结果显示,与传统的A*算法相比较,优化启发搜索策略后的A*算法寻径更快速,更准确,计算效率更高.

An Improved Genetic Algorithm for Flight Path Re-Routes with Reduced Passenger Impact

Adverse weather has serious implications for flight timeliness, as well as passenger and aircraft safety. This often implies that alternative flight paths have to be used by aircraft to avoid adverse weather. To reduce the impact of such path re-routes, exact techniques such as artificial potential field model and Dijkstra’s algorithms have been proposed. However, such approaches are often unsuitable for real time scenarios involving large number of waypoints and constraints. This has led to the use of metaheuristic techniques that give sub-optimal solutions in good time. In this work, an improved genetic algorithm-based technique has been proposed. The algorithm used an improved mutation operator, reduced passenger inconvenience and considered the schedules of aircraft.

Grid-Based Path Planner Using Multivariant Optimization Algorithm

To solve the shortest path planning problems on grid-based map efficiently,a novel heuristic path planning approach based on an intelligent swarm optimization method called Multivariant Optimization Algorithm( MOA) and a modified indirect encoding scheme are proposed. In MOA,the solution space is iteratively searched through global exploration and local exploitation by intelligent searching individuals,who are named as atoms. MOA is employed to locate the shortest path through iterations of global path planning and local path refinements in the proposed path planning approach. In each iteration,a group of global atoms are employed to perform the global path planning aiming at finding some candidate paths rapidly and then a group of local atoms are allotted to each candidate path for refinement. Further,the traditional indirect encoding scheme is modified to reduce the possibility of constructing an infeasible path from an array. Comparative experiments against two other frequently use intelligent optimization approaches: Genetic Algorithm( GA) and Particle Swarm Optimization( PSO) are conducted on benchmark test problems of varying complexity to evaluate the performance of MOA. The results demonstrate that MOA outperforms GA and PSO in terms of optimality indicated by the length of the located path.

Floyd-Warshall Algorithm Based on Picture Fuzzy Information

The Floyd-Warshall algorithm is frequently used to determine the shortest path between any pair of nodes.It works well for crisp weights,but the problem arises when weights are vague and uncertain.Let us take an example of computer networks,where the chosen path might no longer be appropriate due to rapid changes in network conditions.The optimal path from among all possible courses is chosen in computer networks based on a variety of parameters.In this paper,we design a new variant of the Floyd-Warshall algorithm that identifies an All-Pair Shortest Path(APSP)in an uncertain situation of a network.In the proposed methodology,multiple criteria and theirmutual associationmay involve the selection of any suitable path between any two node points,and the values of these criteria may change due to an uncertain environment.We use trapezoidal picture fuzzy addition,score,and accuracy functions to find APSP.We compute the time complexity of this algorithm and contrast it with the traditional Floyd-Warshall algorithm and fuzzy Floyd-Warshall algorithm.