Search

In this paper, a generalized path optimization problem for a weighted digraph (i.e., directed graph) over an additively idempotent semiring was considered. First, the conditions for power convergence of a matrix over an additively idempotent semiring were investigated. Then we proved that the path optimization problem is associated with powers of the adjacency matrix of the weighted digraph. The classical matrix power method for the shortest path problem on the min-plus algebra was generalized to the generalized path optimization problem. The proposed generalized path optimization model encompasses different path optimization problems, including the longest path problem, the shortest path problem, the maximum reliability path problem, and the maximum capacity path problem. Finally, for the four special cases, we illustrate the pictorial representations of the graphs with example data and the proposed method.

The maximum capacity path problem is to find a path connecting two given nodes in a network such that the minimum arc capacity on this path is maximized. The inverse maximum capacity path problem (IMCP) is to modify the capacities of the arcs as little as possible so that a given path becomes maximum capacity path in the modified network. Two cases of IMCP are considered: the capacity of the given path is preserved or not. IMCP is studied and solved both, under any sum-type (e.g., weighted $l_{k}$ norms and sum-type Hamming distance) and max-type distance (e.g., weighted $l_{\infty }$ norm or bottleneck Hamming distance). The obtained algorithms for IMCP are applied to solve a real road transportation network optimization problem.

Finding a widest path to transmit the maximum possible data rate is well-known in the field of computer science. For computational complexity, the network type has a significant impact: It is relatively easy to solve for simple graphs, whereas it is NP-complete for wireless networks based on slotted time models. These models neither facilitate the problem of finding widest paths, nor are they best suited to reflect realistic networks based on IEEE802.11. Therefore, this paper studies the widest path problem for hybrid multi-channel Wireless Mesh Networks (WMNs) without slotted time. In our model, wireless data rates are equally shared among edges within interference range. We prove NP-completeness of the widest path problem (even for a simpler model), but heuristics already demonstrated good results in practical settings.

Shortest path problem in real life applications has to deal with multiple criteria. This article intends to solve a proposed multi-criteria shortest path problem of a weighted connected directed network whose associated edge weights are represented as rough variables in order to tackle the imprecision. We have exhibited two different approaches to determine the optimum path(s) of the proposed problem. The first approach is the proposed modified rough Dijkstra’s labelling algorithm. The second approach considers the rough chance constrained programming technique to formulate the proposed multi-criteria shortest path problem which is eventually solved by two different methods: the goal attainment method and the nondominated sorting genetic algorithm II. These methodologies are numerically illustrated for a multi-criteria weighted connected directed network. Moreover, the simulated results on similar networks of large order and size are analyzed to show the efficiency of the algorithms.

Given an arbitrary directed graph G = ( V , E ) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O ( m ∗ n + m lg n + n T ψ ( m ∗ , n ) ) , where m ∗ is the number of different edges contained in shortest paths and T ψ ( m ∗ , n ) is the running time of an algorithm ψ solving the single-source shortest path problem (SSSP). This is a substantial improvement over a trivial n times application of ψ that runs in O ( n T ψ ( m , n ) ) . In our algorithm we use ψ as a black box and hence any improvement on ψ results also in improvement of our algorithm. A combination of our method, Johnson’s reweighting technique and topological sorting results in an O ( m ∗ n + m lg n ) all-pairs shortest path algorithm for directed acyclic graphs with arbitrary edge lengths. We also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP. Finally, we show how to improve the performance of the proposed algorithm in practice. We then empirically measure the running times of various all-pairs shortest path algorithms on randomly generated graph instances and obtain very promising results.

In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let n and m denote the number of vertices and the number of edges of a given graph. We demonstrate that: • a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line; • the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs; • a shortest path of minimum eccentricity k can be computed in O ( n 2 k + 2 m ) time; • a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in O ( n 3 ) time, in O ( n m ) time, and in O ( m ) time, respectively; • in a graph with a shortest path of eccentricity k, a k-dominating set can be found in n O ( k ) time.

Path planning has become a central problem in motion planning. The classic version of the problem aims to find an obstacle-free path with the minimum length for a given workspace containing a set of obstacles and two sources and destination points. However, some real world applications consider maximizing the path clearance (i.e.,the distance between the robot and obstacles) as the secondary objective. This bi-objective path planning problem has been studied using evolutionary and other heuristic algorithms which do not guarantee achieving Pareto optimal paths. In this paper, we first study this problem using deterministic algorithms. Next, we propose an efficient algorithm for the problem in the grid workspace. We then propose an O(n3) time algorithm for the problem under the Manhattan distance in a continuous workspace containing n vertical segments as obstacles. Finally, we show the obtained solutions are proper approximation for the problem under the Euclidean distance. Introducing a bi-objective length and clearance path planning (bi-PP) model.Proposing an algorithm for solving the bi-PP in grid and finding Pareto fronts.Proposing an algorithm for solving the bi-PP in continuous Manhattan space.Approximating Pareto solutions of the bi-PP under the Euclidean distance.

We consider the single-source shortest path (SSSP) problem: given an undirected graph with integer edge weights and a source vertex $v$ , find the shortest paths from $v$ to all other vertices. In this paper, we introduce a novel parallel algorithm, derived from the Bellman-Ford and Delta-stepping algorithms. We employ various pruning techniques, such as edge classification and direction-optimization, to dramatically reduce inter-node communication traffic, and we propose load balancing strategies to handle higher-degree vertices. These techniques are particularly effective on power-law graphs, as demonstrated by our extensive performance analysis. In the largest tested configuration, an R-MAT graph with $2^{38}$ vertices and $2^{42}$ edges on 32,768 Blue Gene/Q nodes, we have achieved a processing rate of three Trillion Edges Per Second (TTEPS), a four orders of magnitude improvement over the best published results.

In this paper, a unified scheme is proposed for solving the classical shortest path problem and the generalized shortest path problem, which are highly nonlinear. Particularly, the generalized shortest path problem is more complex than the classical shortest path problem since it requires finding a shortest path among the paths from a vertex to all the feasible destination vertices. Different from existing results, inspired by the optimality principle of Bellman’s dynamic programming, we formulate the two types of shortest path problems as linear programs with the decision variables denoting the lengths of possible paths. Then, biased consensus neural networks are adopted to solve the corresponding linear programs in an efficient and distributed manner. Theoretical analysis guarantees the performance of the proposed scheme. In addition, two illustrative examples are presented to validate the efficacy of the proposed scheme and the theoretical results. Moreover, an application to mobile robot navigation in a maze further substantiates the efficacy of the proposed scheme.

In this paper the author introduces the notion of Z-weighted graph or Z-graph in Graph Theory, considers the Shortest Path Problem (SPP) in a Z-graph. The classical Dijkstra’s algorithm to find the shortest path in graphs is not applicable to Z-graphs. Consequently the author proposes a new algorithm called by Z-Dijkstra's Algorithm with the philosophy of the classical Dijkstra's Algorithm to solve the SPP in a Z-graph.

Solving stochastic games with the reachability objective is a fundamental problem, especially in quantitative verification and synthesis. For this purpose, bounded value iteration (BVI) attracts attention as an efficient iterative method. However, BVI’s performance is often impeded by costly end component (EC) computation that is needed to ensure convergence. Our contribution is a novel BVI algorithm that conducts, in addition to local propagation by the Bellman update that is typical of BVI, global propagation of upper bounds that is not hindered by ECs. To conduct global propagation in a computationally tractable manner, we construct a weighted graph and solve the widest path problem in it. Our experiments show the algorithm’s performance advantage over the previous BVI algorithms that rely on EC computation.

We consider directed weighted graphs and define various families of path counting functions. Our main results are explicit formulas for the main term of the asymptotic growth rate of these counting functions, under some irrationality assumptions on the lengths of all closed orbits on the graph. In addition we assign transition probabilities to such graphs and compute statistics of the corresponding random walks. Some examples and applications are reviewed.

The shortest path problem is a classical combinatorial optimization problem with countless real-life applications. Numerous algorithms have been proposed to solve the SPP since the classical Dijkstra algorithm, as well as new approaches to improve the algorithms’ optimality. But according to the real-world transport conditions, researchers began to study variants of this problem which include the time-dependent SPP and the multimodal networks. In this paper, we introduce our new time-dependent shortest path algorithm for multimodal transportation network. The proposed algorithm is a goal-oriented single-source single-destination algorithm. It takes into account the concept of “closeness” to the target node as heuristic to drive the search towards its destination. The optimality of the algorithm is principally based on computing a virtual path which is basically an Euclidean distance from the source to the target aiming at a restriction of the search space.

For path planning algorithms based on visibility graph, constructing a visibility graph is very time-consuming. To reduce the computing time of visibility graph construction, this paper proposes a novel global path planning algorithm, bidirectional SVGA (simultaneous visibility graph construction and path optimization by A⁎). This algorithm does not construct a visibility graph before the path optimization. However it constructs a visibility graph and searches for an optimal path at the same time. At each step, a node with the lowest estimation cost is selected to be expanded. According to the status of this node, different through lines are drawn. If this line is free-collision, it is added to the visibility graph. If not, some vertices of obstacles which are passed through by this line are added to the OPEN list for expansion. In the SVGA process, only a few visible edges which are in relation to the optimal path are drawn and the most visible edges are ignored. For taking advantage of multicore processors, this algorithm performs SVGA in parallel from both directions. By SVGA and parallel performance, this algorithm reduces the computing time and space. Simulation experiment results in different environments show that the proposed algorithm improves the time and space efficiency of path planning.

Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of “shortest” path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is challenging as subpaths of a “shortest” path may not be “shortest” in a temporal graph. We propose efficient algorithms to compute minimum temporal paths and verified their efficiency using large real-world temporal graphs.

In this paper, we study the constrained shortest path tour problem. Given a directed graph with non-negative arc lengths, the aim is to find a single-origin single-destination shortest path, which needs to cross a sequence of node subsets that are given in a fixed order. The subsets are disjoint and may be of different size. In addition, it is required that the path does not include repeated arcs.Theoretical properties of the problem are studied, proving that it belongs to the complexity class NP-complete. To exactly solve it, a Branch & Bound method is proposed. Given the problem hardness, a Greedy Randomized Adaptive Search Procedure is also developed to find near-optimal solutions for medium to large scale instances.Extensive computational experiments, on a significant set of test problems, are carried out in order to empirically evaluate the performance of the proposed approaches. The computational results show that the Greedy Randomized Adaptive Search Procedure is effective in finding optimal or near optimal solutions in very limited computational time. HighlightsA constrained version of the Shortest Path Tour Problem is addressed.Its theoretical properties are analyzed: the problem belongs to the NP-complete class.A Branch & Bound (B&B) and a GRASP are proposed for its solution.The B&B can be used to solve only small size instances.The GRASP is able to address instances of up to 400 nodes in less than 200s.

Proposing a concept of shortest path in uncertain random networks.Designing an algorithm for calculating the chance distribution of path length.Designing an algorithm for finding the shortest path in uncertain random networks. The shortest path problem is one of the most fundamental problems in network optimization. This paper is concerned with shortest path problems in non-deterministic environment, in which some arcs have stochastic lengths and meanwhile some have uncertain lengths. In order to deal with path problems in such network, this paper introduces the chance theory and uses uncertain random variable to describe non-deterministic lengths, based on which two types of shortest path in uncertain random networks are defined. To obtain the shortest paths, an algorithm derived from the Dijkstra Algorithm is proposed. Finally, numerical examples are given to illustrate the effectiveness of the algorithms.

Transport with minimum time cost and distance remains to be an important research area in intelligent transport systems. Shortest path algorithms are primary methods to address simplified problems, which could not be well applied in high-dimensional real situations. We realized the minimum cost and maximum flow result via classical iterative algorithm based on graph theory, adjacency matrix is well applied to express the relationship between transport nodes, a topological sorting transport map is adopted to verify these approaches.

The shortest path problem lies at the heart of network flows that seeks for the paths with minimum cost from source node to sink node in networks. This paper presents a hybrid genetic-ant colony optimization algorithmic approach to the optimal path selection problem. First, some existing solutions for the optimal path selection problem are analyzed, and some shortages and flaws are pointed out. Second, the data organization method for road network based on the graph theory is proposed. Furthermore, the optimal path selection algorithm integrated of sinusoidal probability transfer rules, pheromone update strategy and dual population is presented. Finally, the experimental results show that the proposed algorithm speeds up the convergence rate and improves the efficiency.

This paper deals with the network reliability problem that decides the communication line between main two districts while the  districts were destroyed in military communication network that the  communication lines are connected in  districts. For this problem, there is only in used the mathematical approach as linear programming (LP) software package and has been unknown the polynomial time algorithm. In this paper we suggest the heuristic algorithm with  linear time complexity to solve the optimal solution for this problem. This paper suggests the flow path algorithm (FPA) and level path algorithm (LPA). The FPA is to search the maximum number of distinct paths between two districts. The LPA is to construct the levels and delete the unnecessary nodes and edges. The proposed algorithm can be get the same optimal solution as LP for experimental data. ▸

In the Colorful Path problem we are given a graph G = ( V , E ) and an arbitrary vertex coloring function c : V ? k . The goal is to find a colorful path, i.e., a path on k vertices, that visits each color. This problem has been introduced in the classical work of Alon et al. (1995) 1, and the authors proposed a dynamic programming algorithm that runs in time 2 k n O ( 1 ) and uses O ( 2 k ) space. Since then the only progress obtained is reducing the space size to a polynomial at the cost of using randomization. In this work we show that a progress in time complexity is unlikely: if Colorful Path can be solved in time ( 2 - e ) k n O ( 1 ) , then Set Cover admits a ( 2 - e ' ) n ( n m ) O ( 1 ) -time algorithm. The same applies to other versions of the problem: when edges are colored instead of vertices, or we ask for a walk instead of a path, or when the requested path/walk has specified endpoints.We study also a second, very related problem. In Rainbowst-Connectivity, we are given a k-edge-colored graph and two vertices s and t. The goal is to decide whether there is a rainbow path between s and t, that is, a path on which no color repeats. In its vertex variant (Rainbow Vertexst-Connectivity) the input graph is k-vertex-colored, and a rainbow path is defined analogously. Uchizawa et al. (2011) 14 show that both variants can be solved in 2 k n O ( 1 ) time and exponential space. We show that the space size can be reduced to a polynomial, while keeping the same running time. In contrast to the polynomial space algorithm for Colorful Path, our algorithm for finding rainbow paths is deterministic.

In this paper, we consider solving the all-pairs regular path problem on large graphs efficiently. Let G be a graph and r be a regular path query, and consider finding the answers of r on G. If G is so small that it fits in main memory, it suffices to load entire G into main memory and traverse G to find paths matching r. However, if G is too large and cannot fit in main memory, we need another approach. In this paper, we propose a novel approach based on external memory algorithm. Our algorithm finds the answers matching r by scanning the node list of G sequentially. We made a small experiment, which suggests that our algorithm can solve the problem efficiently.

A group-labeled graph is a directed graph with each arc labeled by a group element, and the label of a path is defined as the sum of the labels of the traversed arcs. In this paper, we propose a polynomial time randomized algorithm for the problem of finding a shortest s-t path with a non-zero label in a given group-labeled graph (which we call the Shortest Non-Zero Path Problem). This problem generalizes the problem of finding a shortest path with an odd number of edges, which is known to be solvable in polynomial time by using matching algorithms. Our algorithm for the Shortest Non-Zero Path Problem is based on the ideas of Bj?rklund and Husfeldt (Proceedings of the 41st international colloquium on automata, languages and programming, part I. LNCS 8572, pp 211---222, 2014). We reduce the problem to the computation of the permanent of a polynomial matrix modulo two. Furthermore, by devising an algorithm for computing the permanent of a polynomial matrix modulo $$2^r$$2r for any fixed integer r, we extend our result to the problem of packing internally-disjoint s-t paths.

Grid graphs are subgraphs of the infinite 2-dimensional integer grid. The Hamiltonian path problem for general grid graphs is a well-known NP-complete problem. In this paper, we present necessary and sufficient conditions for the existence of a Hamiltonian path between two given vertices in L-shaped grid graphs. We also show that a Hamiltonian path between two given vertices of a L-shaped grid graph can be computed in linear time. The Hamiltonian path problem is a well-known NP-complete problem.We give necessary and sufficient conditions for the existence of a Hamiltonian ( s , t ) -path in L-shaped grid graphs.We show that a Hamiltonian ( s , t ) -path in L-shaped grid graph can be computed in linear time if it does exist.

We propose TEDI, an indexing for solving shortest path, and k Nearest Neighbors (kNN) problems. TEDI is based on the tree decomposition methodology. The graph is first decomposed into a tree in which the node contains vertices. The shortest paths are stored in such nodes. These local shortest paths together with the tree structure constitute the index of the graph. Based on this index, algorithms can be executed to solve the shortest path, as well as the kNN problem more efficiently. Our experimental results show that TEDI offers orders-of-magnitude performance improvement over existing approaches on the index construction time, the index size and the query answering. We propose an indexing scheme for efficient graph query processing.We introduce a decomposition algorithm which works for all graphs.We design query answering algorithms for shortest path and kNN.

The longest path problem is a well-known NP-hard problem which can be used to model and solve some optimization problems. There are only a few classes of graphs for which this problem can be solved polynomially. In addition, the results show that the problem is hard to approximate within any reasonable factor for general graphs. We introduce a polynomial-time -approximation algorithm for the longest path problem in solid grid graphs. Our algorithm can also approximate the longest path between any two given boundary vertices of a solid grid graph within the same approximation factor.

Shortest path algorithms for different applications, such as Internet routing, VLSI design and so on are used. Dijkstra and Bellman-Ford are commonly used shortest path algorithms which are typically implemented in networks with hundreds of nodes. However, scale of shortest path problems is increasing, and more efficient algorithms are needed. With the development of multicore processors, one natural way to speedup shortest path algorithms is through parallelization. In this paper, we propose a novel shortest path algorithm with parallel vertex transversal, and compare its speed with standard solutions in datacenter topologies.

Given a grid of cells each having an associated cost value, a raster version of the least-cost path problem seeks a sequence of cells connecting two specified cells such that its total accumulated cost is minimized. Identifying least-cost paths is one of the most basic functions of raster-based geographic information systems. Existing algorithms are useful if the path width is assumed to be zero or negligible compared to the cell size. This assumption, however, may not be valid in many real-world applications ranging from wildlife corridor planning to highway alignment. This paper presents a method to solve a raster-based least-cost path problem whose solution is a path having a specified width in terms of Euclidean distance (rather than by number of cells). Assuming that all cell values are positive, it does so by transforming the given grid into a graph such that each node represents a neighborhood of a certain form determined by the specified path width, and each arc represents a possible transition from one neighborhood to another. An existing shortest path algorithm is then applied to the graph. This method is highly efficient, as the number of nodes in the transformed graph is not more than the number of cells in the given grid and decreases with the specified path width. However, a shortcoming of this method is the possibility of generating a self-intersecting path which occurs only when the given grid has an extremely skewed distribution of cost values.

This paper studies the reliable path problem in the form of minimizing the sum of mean and standard deviation of path travel time. For the case of independent link travel times, we show that the problem can be solved exactly by repeatedly solving a subproblem minimizing the sum of mean and variance of path travel time. The latter is an additive shortest path problem, and can be solved using a standard labeling algorithm. While these subproblems are similar in form to those obtained from Lagrangian relaxation, this formulation admits proof of finite convergence to the optimal solution. An iterative labeling algorithm is developed that solves the non-additive reliable path problem from a single origin to all destinations. Moreover, a labeling technique is employed to further reduce the computational time of the proposed algorithm by partially updating the network in each iteration. As an alternative, a bisection-type search algorithm is developed that solves the problem for the single-origin and single-destination case. Numerical tests are presented, indicating that the proposed algorithm outperform others recently proposed in the literature: unlike Lagrangian relaxation, two of the proposed algorithms find solutions exactly, and the computation time is an order of magnitude faster than outer approximation methods.

Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature.

A new exact algorithm for the constrained shortest path problem is presented.Extensive experiments comparing the behavior of the new scheme and the recent best method from the literature are provided.The proposed approach solves the constrained shortest path problem in USA road networks containing millions of nodes and arcs. We propose an exact method to solve the constrained shortest path (CSP) problem. The new approach takes advantage of the binary partition strategy of a recent K shortest paths (K-SP) algorithm that allows posing numerous additional path constraints in the model without extra difficulty. We adapt and incorporate several pruning strategies from the literature on the CSP problem in this scheme and obtain a robust and scalable algorithm. The method is compared with the current best algorithm to solve the CSP problem and produces significant speedups in a wide range of network configurations. An example is given where the CSP problem is solved in road networks containing a million nodes and arcs.

With the popularity of uncertain data, queries over uncertain graphs have become a hot topic in the database community. As one of the important queries, the shortest path query over an uncertain graph has attracted much attention of researchers due to its wide applications. Although there are some efficient solutions addressing this problem, all existing models ignore an important property existing in uncertain graphs: the correlation among the edges sharing the same vertex. In this paper, we apply Markov network to model the hidden correlation in uncertain graphs and compute the shortest path. Unfortunately, calculating the shortest path and corresponding probability over uncertain graphs modeled by Markov networks is a #P-hard problem. Thus, we propose a filtering-and-verification framework to accelerate the queries. In the filtering phase, we design a probabilistic shortest path index based on vertex cuts and blocks of a graph. We find a series of upper bounds and prune the vertices and edges whose upper bounds of the shortest path probability are lower than the threshold. By carefully picking up the blocks and vertex cuts, the index is optimized to have the maximum pruning capability, so that we can filter a large number of vertices which make no contribution to the final shortest path query results. In the verification phase, we develop an efficient sampling algorithm to determine the final query answers. Finally, we verify the efficiency and effectiveness of our solutions with extensive experiments.

While technological revolution has active role to the increase of computer information, growing computational capabilities of devices, and raise the level of knowledge abilities, and skills. Increase developments in science and technology. In graph used the shortest path algorithms for solving the shortest path problem. The shortest path can be single pair shortest path problem or all pairs shortest path problem. This paper discuss briefly the shortest path algorithms such as Dijkstra's algorithm, Bellman-Ford algorithm,Floyd- Warshall algorithm, and johnson's algorithm. It describes the previous algorithms for solving the shortest path problem. The goal of this paper is to investigate and comparison the impacts of different shortest path algorithms. The study shows that the efficiency varies among algorithms, helps to suggest which one of them ought to be used to solve a specific variant of the shortest path problem.

Image mosaic plays an important role in the fields of computer vision, robot navigation and virtual reality, and has become an active research field in recent years. There is a problem that the error will be accumulated and amplified in the case of aligning multi-images. This paper analyzes the looping path problem causing error accumulation, and introduces a multi-image stitching method based on graph model. We name the algorithm Weighted Shortest Path Algorithm, by which images can be stitched automatically. Matching Mean Square Error is introduced as the weight of edges on the graph, which is intuitive and easy to compute. Furthermore, the optimized Dijkstra algorithm is applied to speed up the path finding algorithm. Experiments show that the proposed algorithm causes less Matching Mean Square Error and obtains more stable results than other similar methods. Moreover, we extended our model to 360 ° panoramic image generation, and the quality of the stitched panorama is quite good.

An energy‐optimal coverage path planning algorithm is proposed for environment survey. First, 3D terrains are modelled by tensor product Bezier surfaces for a mesh representation. Then, a power estimator is derived to calculate the consumed energy for a piecewise spatial path. Based on the digital surface model, an energy consumption map is constructed for the whole area by means of a weighted directed graph. Finally, an energy‐optimal path can be achieved through traversing the map by a genetic algorithm. Numerical experiments demonstrate the effectiveness and efficiency of the proposed algorithm.

Ravi et?al. 2 provide a polynomial-time exact solution to the problem of finding a minimum-cost spanning tree with k vertices on the boundary of a convex region and a faster algorithm for the special case of all vertices lying on a circle. In this paper we show that the latter algorithm generally does not solve the kMST problem on circles. A new algorithm is presented that solves the problem in a slightly more general way and with a better complexity.

Among the main issues in the theory of geometric grids on spatial information systems, is the problem of finding the shortest path routing between two points. In this paper tried to using the graph theory and A* algorithms in transport management, the optimal method to find the shortest path with shortest time condition to be reviewed. In order to construct a graph that consists of a network of pathways and modelling of physical and phasing area, the shortest path routes, elected with the use of the algorithm is modified A*.At of the proposed method node selection Examining angle nodes the desired destination node and the next node is done. The advantage of this method is that due to the elimination of some routes, time of route calculation is reduced.

Given an edge-weighted graph G and two distinct vertices s and t of G, the next-to-shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an On3-time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 653, 205-211 2015

This paper presents a method for incremental updating on consumer electronic devices, called differential compression based on Dijkstra algorithm (DDIFF). It describes the similarities between the old and new versions as a directed weighted graph. In the graph, the shortest path between the start and end vertices corresponds to the minimal delta. As a result, the delta-encoding problem is reduced to the single-source shortest path problem. Experiments show that the proposed method is feasible, and average data transmission saving is as high as 69.3%. In comparison with the existing methods, DDIFF constructs the minimal patch, and the patch costs less time to apply1.

Given a directed acyclic graph and a set of vertex pairs, an antisymmetric path is a directed path that does not contain vertices from the same pair in the set. The goal of the Longest Antisymmetric Path problem is to determine the longest antisymmetric path that connects two given vertices in the graph. The problem has important applications in software testing and bioinformatics. The problem is known to be NP-hard. In this paper, we study the computational lower bound of the problem, we show that the problem cannot be solved in time 2 o ( n 1 3 ) unless 3SAT can be solved in subexponential time. In addition, we study the inapproximability of the problem and show that the problem cannot be approximated within a ratio of ( n - 2 ) 2 in polynomial time unless P = NP . Our technique also suggests that both the lower bound and inapproximability also hold for directed acyclic graphs of degree at most 6.

In this paper, an attempt is made to solve the problem of finding an efficient point-to-point shortest path algorithm for graphs of larger sizes. First run the A * algorithm with binary heap implementation from both the directions. The nodes extracted from both directions are saved and then genetic algorithm is used to find the shortest path. The bi-directional strategy reduces the search space and the genetic algorithm optimizes the search problem to give best result. The final results illustrates that this novel approach with the optimization strategies achieves high scalability and performance.

The problem of finding the Hamiltonian path in a graph, or deciding whether a graph has a Hamiltonian path or not, is an NP-complete problem. No exact solution has been found yet, to solve this problem using polynomial amount of time and space. In this paper, we propose a two dimensional (2-D) optical architecture based on optical electronic devices such as micro ring resonators, optical circulators and MEMS based mirror (MEMS-M) to solve the Hamiltonian Path Problem, for undirected graphs in linear time. It uses a heuristic algorithm and employs n +1 different wavelengths of a light ray, to check whether a Hamiltonian path exists or not on a graph with n vertices. Then if a Hamiltonian path exists, it reports the path. The device complexity of the proposed architecture is O( n 2 ).

SUMMARY Given an edge-weighted tree with n vertices and a positive integer L, the length-constrained maximum-density path problem is to find a path of length at least L with maximum density in the tree. The density of a path is the sum of the weights of the edges in the path divided by the number of edges in the path. We present an O(n) time algorithm for the problem. The previously known algorithms run in O(nL )o rO(nlogn) time.

K-shortest path algorithm is generalization of the shortest path algorithm. K-shortest path is used in various fields like sequence alignment problem in molecular bioinformatics, robot motion planning, path finding in gene network where speed to calculate paths plays a vital role. Parallel implementation is one of the best ways to fulfill the requirement of these applications. A GPU based parallel algorithm is developed to find k number of shortest path in a positive edge-weighted directed large graph. In calculated shortest path repetition of the vertices is not allowed. Implemented algorithm calculates a k-shortest path between two pair of vertices of a graph with n nodes and m vertices. This approach is based on Yen's algorithm to find k-shortest loopless path. We implemented our algorithms in Nvidia's GPU using Compute Unified Device Architecture (CUDA). This paper presents comparative analysis between CPU and GPU based implementation of Yen's Algorithm. Our approach achieves the 6 time speed up in comparison of serial algorithm.

Path planning has been an important aspect in the development of autonomous cars in which path planning is used to find a collision-free path for the car to traverse from a starting point Sp to a target point Tp. The main criteria for a good path planning algorithm include the capability of producing the shortest path with a low computation time. Low computation time makes the autonomous car able to re-plan a new collision-free path to avoid accident. However, the main problem with most path planning methods is their computation time increases as the number of obstacles in the environment increases. In this paper, an algorithm based on visibility graph (VG) is proposed. In the proposed algorithm, which is called Equilateral Space Oriented Visibility Graph (ESOVG), the number of obstacles considered for path planning is reduced by introducing a space in which the obstacles lie. This means the obstacles located outside the space are ignored for path planning. From simulation, the proposed algorithm has an improvement rate of up to 90% when compared to VG. This makes the algorithm is suitable to be applied in real-time and will greatly accelerate the development of autonomous cars in the near future.