Search

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.

We consider the well-known geometric problem of determining shortest paths between pairs of points on a polyhedral surface P, where P consists of triangular faces with positive weights assigned to them. The cost of a path in P is defined to be the weighted sum of Euclidean lengths of the sub-paths within each face of P. We present query algorithms that compute approximate distances and/or approximate shortest paths on P. Our all-pairs query algorithms take as input an approximation parameter e∈(0,1) and a query time parameter $\mathfrak{q}$, in a certain range, and build a data structure $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$, which is then used for answering e-approximate distance queries in $O(\mathfrak{q})$time. As a building block of the $\mathrm{APQ}(P,\varepsilon;\mathfrak{q})$data structure, we develop a single-source query data structure SSQ(a;P,e) that can answer e-approximate distance queries from a fixed point a to any query point on P in logarithmic time. Our algorithms answer shortest path queries in weighted surfaces, which is an important extension, both theoretically and practically, to the extensively studied Euclidean distance case. In addition, our algorithms improve upon previously known query algorithms for shortest paths on surfaces. The algorithms are based on a novel graph separator algorithm introduced and analyzed here, which extends and generalizes previously known separator algorithms.

A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to find a shortest descending path from s to t in a polyhedral terrain. We give some properties of such paths. In the case where the face sequence is specified, we show that the shortest descending path is unique, and use convex optimization to give an ϵ-approximation algorithm that computes the path in O(n3.5log(1ϵ)) time.

A graph G is panconnected if each pair of distinct vertices u,v@?V(G) are joined by a path of length l for all d"G(u,v)=

In this paper, the convexity properties of fuzzy nets on the Euclidean space R d is investigated.

In this paper, we are interested in the shortest path problem between two specified vertices in digraphs containing negative cycles. We study two integer linear formulations and their linear relaxations. A first formulation, close in spirit to a classical formulation of the traveling salesman problem, requires an exponential number of constraints. We study a second formulation that requires a polynomial number of constraints and, as confirmed by computational experiments, its linear relaxation is significantly sharper. From the second formulation we propose a family of linear relaxations with fewer variables than the classical linear one.

An orthogonal spanner network for a given set of n points in the plane is a plane straight line graph with axis-aligned edges that connects all input points. We show that for any set of n points in the plane, there is an orthogonal spanner network that (i) is short having a total edge length at most a constant times the length of a Euclidean minimum spanning tree for the point set; (ii) is small having O(n) vertices and edges; and (iii) has constant geometric dilation, which means that for any two points u and v in the network, the shortest path in the network between u and v is at most a constant times longer than the Euclidean distance between u and v. Such a network can be constructed in O(nlogn) time.

This paper considers the generation of the origin-destination (OD) matrix, basic data in any vehicle routing or traveling salesman problem. An OD matrix must be generated by calculating the shortest paths between some nodes. Candidate methods for this are repetitive use of one-to-all shortest path algorithms such as Dijkstra's algorithm, use of all-to-all shortest path algorithms such as the Floyd-Warshall algorithm, and use of specifically designed some-to-some shortest path algorithms. This paper compares the performance of several shortest path algorithms in computing OD matrices on real road networks. Dijkstra's algorithm with approximate bucket data structure performed the best for most of the networks tested. This paper also proposes a grouping-based algorithm for OD matrix generation. Although it is an approximation approach, it has several good characteristics: it can find the exact shortest distances for most OD pairs; it guarantees that all the calculated shortest path distance values have corresponding paths; the deviation of any distance from the corresponding true shortest distance is small; and its computation time is short.

We generalize our optimal-time algorithm for computing (an implicit representation of) the shortest-path map from a fixed source s on the surface of a convex polytope P to three realistic scenarios where P is a possibly nonconvex polyhedron. In the first scenario, ∂ P is a terrain whose maximum facet slope is bounded by any fixed constant. In the second scenario, P is an uncrowded polyhedron—each axis-parallel square h of side length l(h) whose smallest Euclidean distance to a vertex of P is at least l(h) is intersected by at most O(1) facets of ∂ P—an input model which, as we show, is a generalization of the well-known low-density model. In the third scenario, P is self-conforming—here, for each edge e of P, there is a connected region R(e) of O(1) facets whose union contains e, so that the shortest path distance from e to any edge e′ of ∂ R(e) is at least c⋅max {|e|,|e′|}, where c is some positive constant. In particular, it includes the case where each facet of ∂ P is fat and each vertex is incident to at most O(1) facets of ∂ P. In all the above cases the algorithm runs in O(nlog n) time and space, where n is the number of edges of P, and produces an implicit representation of the shortest-path map, so that the shortest path from s to any query point q can be determined in O(log n) time. The constants of proportionality depend on the various parameters (maximum facet slope, crowdedness, etc.). We also note that the self-conforming model allows for a major simplification of the algorithm.

In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300306, 1999), it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by , a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio and give an improved bound of . Our main result is an upper bound of independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229240, 2001) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339356, 2004). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is .

The hierarchical median problem asks for a hierarchical sequence of solutions to the k-median problems of growing cardinality. The best algorithm known for this problem in the general metric case has competitive ratio 20.71. In the paper, the case is under study that the clients and facilities lie on the real line, as well as the case of a Euclidean space. An algorithm is proposed with competitive ratio 8 in the case of the real line, and 8 + 4√2 (approximately 13.66), in the Euclidean case.

We consider a shortest path problem, where the travel times on the arcs may vary with time and waiting at any node is allowed. Simple adaptations of the Dijkstra algorithm may fail to solve the problem, when discontinuities exist. We propose a new Dijkstra-like algorithm that overcomes these difficulties.

We prove asymptotic formulae with two significant terms for the expectation and variance of the random variable when the variables and range over the set and , where is the number of steps in the Euclidean algorithm applied to the numbers? and?.

In the real world, there are many phenomena that occur on a network or alongside a network; for example, traffic accidents on highways and retail stores along streets in an urbanized area. In the literature, these phenomena are analysed under the assumption that distance is measured with Euclidean distance on a plane. This paper first examines this assumption and shows an empirical finding that Euclidean distance is significantly different from the shortest path distance in an urbanized area if the distance is less than 500 m. This implies that service areas in urbanized areas cannot be well represented by Voronoi diagrams defined on a plane with Euclidean distance, termed generalized planar Voronoi diagrams. To overcome this limitation, second, this paper formulates six types of Voronoi diagrams defined on a network, termed generalized network Voronoi diagrams, whose generators are given by points, sets of points, lines and polygons embedded in a network, and whose distances are given by inward/outward distances, and additively/multiplicatively weighted shortest path distances. Third, in comparison with the generalized planar Voronoi diagrams, the paper empirically shows that the generalized network Voronoi diagrams can more precisely represent the service areas in urbanized areas than the corresponding planar Voronoi diagrams. Fourth, because the computational methods for constructing the generalized planar Voronoi diagrams in the literature cannot be applied to constructing the generalized network Voronoi diagrams, the paper provides newly developed efficient algorithms using the 'extended' shortest path trees. Last, the paper develops user-friendly tools (that are included in SANET, a toolbox for spatial analysis on a network) for executing these computational methods in a GIS environment.

The occlusion of feature points and/or feature points leaving the field of view of a camera is a significant practical problem that can lead to degraded performance or instability of visual servo control and vision-based estimation algorithms. By assuming that one known Euclidean distance between two feature points in an initial view is available, homography relationships and image geometry are used in this paper to determine the Euclidean coordinates of feature points in the field of view. A new daisy-chaining method is then used to relate the position and orientation of a plane defined by the feature points to other feature-point planes that are rigidly connected. Through these relationships, the Euclidean coordinates of the original feature points can be tracked even as they leave the field of view. This objective is motivated by the desire to track the Euclidean coordinates of feature points on one face of a satellite as it continually rotates and feature points become self-occluded. A numerical simulation is included to demonstrate that the Euclidean coordinates can be tracked even when they leave the field of view. However, the results indicate the need for a method to reconcile any accumulated error when the feature points return to the field of view.

One of the most important kinds of queries in Spatial Network Databases (SNDB) to support location-based services (LBS) is the shortest path query. Given an object in a network, e.g. a location of a car on a road network, and a set of objects of interests, e.g. hotels, gas station, and car, the shortest path query returns the shortest path from the query object to interested objects. The studies of shortest path query have two kinds of ways, online processing and preprocessing. The studies of preprocessing suppose that the interest objects are static. This paper proposes a shortest path algorithm with a set of index structures to support the situation of moving objects. This algorithm can transform a dynamic problem to a static problem. In this paper we focus on road networks. However, our algorithms do not use any domain specific information, and therefore can be applied to any network. This algorithm’s complexity is O( k log 2 i ), and traditional Dijkstra’s complexity is O(( i + k ) 2 ).

Given a set P of points (clients) in the plane, a Euclidean 2-centre of P is a set of two points (facilities) in the plane such that the maximum distance from any client to its nearest facility is minimized. Geometrically, a Euclidean 2-centre of P corresponds to a cover of P by two discs of minimum radius r (the Euclidean 2-radius). Given a set of mobile clients, where each client follows a continuous trajectory in the plane with bounded velocity, the motion of the corresponding mobile Euclidean 2-centre is not necessarily continuous. Consequently, we consider strategies for defining the trajectories of a pair of mobile facilities that guarantee a fixed-degree approximation of the Euclidean 2-centre while maintaining bounded relative velocity. In an attempt to balance the conflicting goals of closeness of approximation and a low maximum relative velocity, we introduce reflection-based 2-centre functions by reflecting the position of a mobile client across the mobile Steiner centre and the mobile rectilinear 1-centre, respectively.

In this paper, we present a hill-jump algorithm of the Hopfield neural network for the shortest path problem in communication networks, where the goal is to find the shortest path from a starting node to an ending node. The method is intended to provide a near-optimum parallel algorithm for solving the shortest path problem. To do this, first the method uses the Hopfield neural network to get a path. Because the neural network always falls into a local minimum, the found path is usually not a shortest path. To search the shortest path, the method then helps the neural network jump from local minima of energy function by using another neural network built from a part of energy function of the problem. The method is tested through simulating some randomly generated communication networks, with the simulation results showing that the solution found by the proposed method is superior to that of the best existing neural network based algorithm.

The Generalized Cardinality-Constrained Shortest Path Problem (GCCSPP) consists in finding the minimum cost path in a digraph, using at most r arcs in a subset F of the arc set. We propose an algebraic characterization of the extreme points of the associated polytope, and then we show that it is equivalent to the geometric one, obtained extending to the GCCSPP some known results for the cardinality-constrained shortest path problem.

Generalized network problems describe situations in which flow can be generated or consumed through arcs. This research considers generalized shortest path problem in stochastic environment in which the changing rate of flow is random. To satisfy the demands of decision makers, three types of models have been formulated to solve the generalized shortest path problem under different decision criteria. The PSO algorithm is build to solve the generalized shortest path problem in stochastic environment. Finally, a numerical example is given to illustrate the effectiveness of the given algorithm.

We consider the problem of computing shortest paths in three-dimensions in the presence of a single-obstacle polyhedral terrain, and present a new algorithm that for any p>=1, computes a ([email protected])-approximation to the L"p-shortest path above a polyhedral terrain in O([email protected]) time and O(nlogn) space, where n is the number of vertices of the terrain, and c=2^(^p^-^1^)^/^p. This leads to a FPTAS for the problem in L"1 metric, a ([email protected])-factor approximation algorithm in Euclidean space, and a 2-approximation algorithm in the general L"p metric.

Recently a new least-squares primal-dual (LSPD) algorithm, that is impervious to degeneracy, has effectively been applied to solving linear programming problems by Barnes et al., 2002. In this paper, we show an application of LSPD to shortest path problems with nonnegative arc length is equivalent to the Dijkstra's algorithm. We also compare the LSPD algorithm with the conventional primal-dual algorithm in solving shortest path problems and show their difference due to degeneracy in solving the 1-1 shortest path problems.

The watchman route problem (WRP) was first introduced in 1988 and is defined as follows: How to calculate a shortest route completely contained inside a simple polygon such that any point inside this polygon is visible from at least one point on the route? So far the best known result for the WRP is an O(n(3) log n) runtime algorithm (with inherent numerical problems of its implementation). This paper gives an k(epsilon) x O(kn) approximate algorithm for WRP by using a rubberband algorithm, where n is the number of vertices of the simple polygon, k the number of essential cuts, epsilon the chosen accuracy constant for the minimization of the calculated route, and k(epsilon) equals the length of the initial route minus the length of the calculated route, divided by epsilon.

We demonstrate that a simple model of P. polycephalum can be used to compute shortest paths between two points in a graph. Reminiscent of how the real organism behaves in a maze when presented with two distinct food sources s and t, the algorithm gradually identifies the shortest s-t path by retreating from everywhere else in the graph.

In this paper, we consider a classical Bi-objective Shortest Path problem (BSP) that takes into account both distance and insecurity criteria. This work is in collaboration with an enterprise who provide a web platform called Géovélo that aims to propose routes for cycling. We propose a new exact method to solve a BSP, called Label Setting algorithm with Dynamic update of Pareto Front (LSDPF), which aims to find all nondominated solutions of the problem. Different exploration strategies have been proposed and tested. Numerical experiments on real data sets and on instances of the literature were conducted. Comparison with recent benchmarks algorithms solving BSP-the bounded Label Setting algorithm by (Raith, 2010) and the pulse algorithm by (Duque et al., 2015)-shows that our method outperform these benchmarks algorithms.

The minmax regret robust shortest path problem aims at finding a path that minimizes the maximum deviation from the shortest paths over all scenarios. It is assumed that different arc costs are associated with different scenarios. This paper introduces a technique to reduce the network, before a minmax regret robust shortest path algorithm is applied. The preprocessing method enhances others explored in previous research. The introduced method acts dynamically and allows to update the conditions to be checked as new network nodes that can be discarded are identified. Computational results on random and Karasan networks are reported, which compare the dynamic preprocessing algorithm and its former static version. Two robust shortest path algorithms as well as the resolution of a mixed integer linear formulation by a solver are tested with and without these preprocessing rules.

We consider a search algorithm for the output distribution that achieves the channel capacity of a discrete memoryless channel. We will propose an algorithm by iterated projections of an output distribution onto affine subspaces in the set of output distributions. The problem of channel capacity has a similar geometric structure as that of smallest enclosing circle for a finite number of points in the Euclidean space. The metric in the Euclidean space is the Euclidean distance and the metric in the space of output distributions is the Kullback-Leibler divergence. We consider these two problems based on Amari's $\alpha$-geometry. Then, we first consider the smallest enclosing circle in the Euclidean space and develop an algorithm to find the center of the smallest enclosing circle. Based on the investigation, we will apply the obtained algorithm to the problem of channel capacity., Comment: 45 pages, 9 figures, submitted to IEEE Transactions on Information Theory

Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm solves the shortest path problem in social graphs modelling sites with over 100 million users with acceptable response time (50 ms per query), memory usage (less than 15 GB of the primary memory) and applicable accuracy (higher than 90% of the queries return exact result). peerReviewed

This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node minus 1, since it determines the shortest path from all the nodes in the graph, starting from the first node. Therefore, Dijkstra algorithm might not be able to provide the information on every second, searching for the shortest path between the roads of the congested city and the destination. In order to solve these problems, this paper chooses a method of searching a number of nodes at once by means of choosing the shortest path of all the path nodes (select of minimum weight arc in-degree and out-degree), excluding the departure and destination nodes, and of choosing all the arcs that coincide with the shortest path of the path nodes, from all the node outgoing arcs starting from the departure node. On applying the suggested algorithm to 14 various digraphs, we succeeded to search the shortest path. In addition, the result was obtained at the speed of 2 to 3 times faster than that of Dijkstra algorithm, and the memory required was less than that of Dijkstra algorithm.

A partial order relation is introduced on the set of all paths. An algorithm for determination of the shortest paths is considered providing an additional condition on the partial order is assumed.

Lately, it has been proposed to use shortest path first routing to implement Traffic Engineering in IP networks. The idea is to set the link weights so that the shortest paths, and the traffic thereof, follow the paths designated by the operator. Clearly, only certain shortest path representable path sets can be used in this setting, that is, paths which become shortest paths over some appropriately chosen positive, integer-valued link weights. Our main objective in this paper is to distill and unify the theory of shortest path representability under the umbrella of a novel flow-theoretic framework. In the first part of the paper, we introduce our framework and state a descriptive necessary and sufficient condition to characterize shortest path representable paths. Unfortunately, traditional methods to calculate the corresponding link weights usually produce a bunch of superfluous shortest paths, often leading to congestion along the unconsidered paths. Thus, the second part of the paper is devoted to reducing the number of paths in a representation to the bare minimum. To the best of our knowledge, this is the first time that an algorithm is proposed, which is not only able to find a minimal representation in polynomial time, but also assures link weight integrality. Moreover, we give a necessary and sufficient condition to the existence of a one-to-one mapping between a path set and its shortest path representation. However, as revealed by our simulation studies, this condition seems overly restrictive and instead, minimal representations prove much more beneficial.

In this paper, we present an efficient visibility-based algorithm for determining a locally exact shortest path (LESP) from a source point to a destination point on a (triangulated) polyhedral surface. Our algorithm, of a finitely-iterative scheme, evolves an initial approximately shortest path into a LESP. During each iteration, we first compute the exact shortest path restricted on the current face sequence according to Fermat's principle which affirms that light always follows the shortest optical path, and then optimize the face sequence where the path is not locally shortest on the polyhedral surface. Since the series of paths we obtained are monotonic decreasing in length, the algorithm gives a LESP which is shorter than the initial path, at conclusion. For comparison, we use various methods to provide an initial path. One of the methods is Dijkstra's algorithm, and the others are the Fast Marching Method (FMM) and its improved version. Our intention for improvement is to overcome the limitation of acute triangulations in the original version. To achieve this goal, we classify all the edges into seven types according to different wavefront propagation manners, and dynamically determine the type of each edge for controlling the subsequent wavefront expansion. Furthermore, we give two approaches for backtracing the approximately shortest paths directed at the improved FMM. One exploits the known propagation manners of the edges as well as the Euler's method. This is another contribution in this paper.

Given an mxn matrix A, n Euclidean distances, those from each column to the space spanned by the remaining columns of A, are considered. An elegant relationship between A, these Euclidean distances, and the solutions of n simple linear least squares problems arising from A is derived. When A has full column rank, from this a useful expression for these Euclidean distances is immediately obtained. The theory is then used to greatly improve the efficiency of an algorithm used in communications.

We show that every n-point metric of negative type (in particular, every n-point subset of L 1) admits a Frechet embedding into Euclidean space with distortion $O(\sqrt{\log n}\cdot \log \log n)$, a result which is tight up to the O(log log n) factor, even for Euclidean metrics. This strengthens our recent work on the Euclidean distortion of metrics of negative into Euclidean space.

We study the non-rigidity of Euclidean $t$-designs, namely we study when Euclidean designs (in particular certain tight Euclidean designs) can be deformed keeping the property of being Euclidean $t$-designs. We show that certain tight Euclidean $t$-designs are non-rigid, and in fact satisfy a stronger form of non-rigidity which we call strong non-rigidity. This shows that there are plenty of non-isomorphic tight Euclidean $t$-designs for certain parameters, which seems to have been unnoticed before. We also include the complete classification of tight Euclidean $2$-designs., 21 pages

In this paper, we study the problem of finding the shortest path in circulant graphs with an arbitrary number of jumps. We provide algorithms specifically tailored for weighted undirected and directed circulant graphs with two jumps which compute the shortest path. Our method only requires O(logN) arithmetic operations and the total bit complexity is O(log2NloglogNlogloglogN), where N is the number of the graph’s vertices. This elementary and efficient shortest path algorithm has been derived from the Closest Vector Problem (CVP) of lattices in dimension two and with an ℓ1 norm.

In real road networks, the presence of no-left, no-right or no U-turn signs, restricts the movement of vehicles at intersections. These turn prohibitions must be considered when calculating the shortest path between a starting and an ending point in a road network. We propose an extension of Dijkstra’s algorithm to solve the shortest path problem with turn prohibitions. The method uses arc labeling and a network structure with low memory requirements. We compare the proposed method with the dual graph approach in a set of randomly generated networks and Bogota’s large-scale road network. Our computational experiments show that the performance of the proposed method is better than that of the dual graph approach, both in terms of computing time and memory requirements. We co-developed a Web-based decision support system for computing shortest paths with turn prohibitions that uses the proposed method as the core engine.

A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an optimal control problem. Then the resulting distributed control problem is expressed in measure theoretical form, in fact an infinite dimensional linear programming problem. The optimal measure representing the shortest path problem is approximated by the solution of a finite dimensional linear programming problem.

Given a polyhedral terrain with n vertices, the shortest monotone descent path problem deals with finding the shortest path between a pair of points, called source (s) and destination (t) such that the path is constrained to lie on the surface of the terrain, and for every pair of points p=(x(p),y(p),z(p)) and q=(x(q),y(q),z(q)) on the path, if dist(s,p)

The Euclidean distance transform of a binary image is the function that assigns to every pixel the Euclidean distance to the background. The Euclidean feature transform is the function that assigns to every pixel the set of background pixels with this distance. We present an algorithm to compute the exact Euclidean feature transform sets in linear time. The algorithm is applicable in arbitrary dimensions. (c) 2006 Elsevier B.V. All rights reserved.

New properties of convex sets and their inscribed 2n-gons in a two dimensional Euclidean space are presented. As an application, these results solve a question from functional analysis.

Common network parameters, such as number of nodes and arc lengths are frequently subjected to ambiguity as a result of probability law. A number of authors have discussed the calculation of the shortest path in networks with random variable arc lengths. Generally, only a subset of intermediate nodes chosen in accordance with a given probability law can be used to transition from source node to sink node. The determination of a priori path of the minimal length in an incomplete network is defined as a probabilistic shortest path problem. When arc lengths between nodes are randomly assigned variables in an incomplete network the resulting network is known as an incomplete stochastic network. In this paper, the computation of minimal length in incomplete stochastic networks, when travel times between nodes are allowed to be exponentially distributed random variables, is formulated as a linear programming problem. A practical application of the methodology is demonstrated and the results and process compared to the Kulkarni’s [V.G. Kulkarni, Shortest paths in networks with exponentially distributed arc lengths, Networks 16 (1986) 255–274] method.

We prove superlinear lower bounds for some shortest path problems in directed graphs, where no such bounds were previously known. The central problem in our study is the replacement paths problem: Given a directed graph G with non-negative edge weights, and a shortest path P = { e 1 , e 2 , …, e p } between two nodes s and t , compute the shortest path distances from s to t in each of the p graphs obtained from G by deleting one of the edges e i . We show that the replacement paths problem requires Ω( m √ n ) time in the worst case whenever m = O ( n √ n ). Our construction also implies a similar lower bound on the k shortest simple paths problem for a broad class of algorithms that includes all known algorithms for the problem. To put our lower bound in perspective, we note that both these problems (replacement paths and k shortest simple paths) can be solved in near-linear time for undirected graphs.

This paper considers the shortest path problem with fuzzy arc lengths. According to different decision criteria, the concepts of expected shortest path, α-shortest path and the most shortest path in fuzzy environment are originally proposed, and three types of models are formulated. In order to solve these models, a hybrid intelligent algorithm integrating simulation and genetic algorithm is provided and some numerous examples are given to illustrate its effectiveness.

Shortest path problems occupy an important position in operations research as well as in artificial intelligence. In this paper we study shortest path algorithms that exploit heuristic estimates. The well-known algorithms are put into one framework. Besides, we present an interesting application of binary numbers in the shortest path theory.

Let p and q be two points on the surface of a polytope Pi. This paper provides a rubberband algorithm for computing a Euclidean shortest path between p and q (a so-called surface ESP) that is contained on the surface of Pi. The algorithm has k(1)(epsilon).k(2)(epsilon).O(n(2)) time complexity, where n is the number of vertices of Pi, k(i)(epsilon) = (L-0i - L-i)/epsilon, for the true length L-i of some shortest path with initial (polygonal path) length L-0i (used when approximating this shortest path), for i = 1, 2. Rubberband algorithms follow a straightforward design strategy, and the proposed algorithm is easy to implement and thus of importance for applications, for example, when analyzing 3D objects in 3D image analysis, such as in biomedical or industrial image analysis, using 3D image scanners.

Dijkstra's algorithm is a classic algorithm for finding the shortest path between two points due to its optimisation capability. The adjacency matrix is the naive storage structure of the algorithm. This storage structure has limited the use of the algorithm as it expands large storage space. A multi-layer dictionary is proposed in this work to enhance the storage structure. Previously, the algorithm was used to optimise single parameter (such as distance, time and fuel) for movement between two places. The path computed using the classic Dijkstra's algorithm is the shortest; however, it may not be the most feasible. The algorithm needs to optimise other factors such as energy consumption and the degree of turns a robot need to take. Junction degree of difficulty function is introduced to further improve the output. It is defined as the degree of difficulty of the path between two points in an open environment. The experimental result shows that the proposed path planning method produced the most optimal path between two points when applied to a map of any indoor terrain.