Search

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.

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nl) respectively, where n is the number of vertices of the grid and l is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.

Path planning is used to solve the problem of moving an agent towards a destination. Theta* is a well know any angle path planning algorithm which works by utilizing line of sight checks during the search. To find shorter paths that are not constraint to grid edges, there is a compromise in the time taken to reach the destination which makes Theta* undesirable as the grid map size increases. To solve this problem and enhance the search performance we propose a method which divides a map into high and low density regions using an unsupervised clustering algorithm based on the number of blocked nodes on a grid map. After comparing the proposed model with theta* the results show the time taken to find the shortest path to be reduced significantly in comparison with Theta* while the path length will remain as short as Theta.

Path planning is one of the most studied problems in the field of robotics, unmanned aerial vehicles (uavs), vehicle navigation and fields like these. The majority algorithms of path planning produce possible paths of grid graph, and then apply in problems such as classical graph route searching. Astar algorithm, Hierarchical Path-Finding A-star (HPA*) and Jump Point Search (JPS) algorithms are studied in this paper to compare the maze searching capacity and different search maps' efficiency. We also propose an improved JPS algorithm in symmetric grid graph. In this paper, we compare their search time and efficiency. Conducted experiment shows that by adopting the same benchmarks our algorithm not only tackles the congestion problem, but also solves the problem more efficiently. Experiments validated the improved JPS algorithm and results show it outperforms the other algorithms.

In this paper heuristics are proposed for finding the shortest loopless path, from a source node to a target node, that visits a given set of nodes in a directed graph, such that it can be protected using a node-disjoint path. This type of problem may arise due to network management constraints. The problem of calculating the shortest path that visits a given set of nodes is at least as difficult as the traveling salesman problem, and it has not received much attention. Nevertheless an efficient integer linear programming (ILP) formulation has been recently proposed for this problem. Here, the ILP formulation is adapted to include the constraint that the obtained path will be able to be protected by a node-disjoint path. Computational experiments show that this approach, namely in large networks, may fail to obtain a solution in a reasonable amount of time. Therefore three versions of a heuristic are proposed, for which extensive computational results show that they are able to find a solution in most cases, and that the calculated solutions present an acceptable relative error regarding the cost of the optimal active path. Further the CPU time required by the heuristics is significantly smaller than the required by the used ILP solver.

International audience; The computation of the k-shortest paths, should they be elementary or not, has been extensively investigated in the literature, yielding to extremely performant algorithms. For elementary paths, the best known algorithm to this day is the algorithm of Yen enhanced by the extension of Lawler,while for the search of non-elementary paths, the algorithm with the best complexity is due to Eppstein but is outperformed in practice by the Recursive Enumeration Algorithm. In the context of transportation networks, graphs are time dependent, meaning that the cost of an edge depends on the time at which it is crossed. If for each edge one cannot arrive later if he departs earlier, the network is said to respect the FIFO property. Underthis hypothesis, the usual Dijkstra shortest path algorithm is still polynomial. Additionally, since each edge is associated to a transportation type, one may want to restrict a path to be in a regular language. To find a shortest path under this constraint a polynomial algorithm, called DRegLC, works on the product of the network and the graph representing an automaton accepting the regular language.In this paper, some k-shortest paths algorithms are adapted to be used on such transportation networks with a regular language constraint. Also, the computation of the k-shortest elementary paths is considered using k-shortest non elementary paths algorithms, deleting loops while searching if possible. To address this approach, a new algorithm is presented to speedup the search of elementary paths while scanning as few paths containing loops as possible.

The A* algorithm and its modifications are commonly used in graph searching for mobile robot path planning. However in case of large open list sizes the A* algorithm needs significant time to find the solution due to the open list sorting procedure which determines the computational complexity of A*. This paper presents a new approach called L* which improves the A* graph searching algorithm and provides linear computational complexity due to the lack of the open list sorting procedure. This is a crucial factor in order to decrease the time consumption for large open list sizes in a graph searching algorithm.

The shortest path problem, one of classic topic in the field of Graph Theory and path search, majors in the method about how to find the shortest path between two nodes in a directed-graph. Based on observing the relationship between water flow rate and pipe diameter in a pipeline network, the paper puts forward a kind of multi-thread parallel path search algorithm deriving of Hydrokinetics, namely Water flow Search Algorithm, WFS. Besides, the author has designed a multi-thread program to conduct test. It has been proved that WFS is of great feasibility and applicability to deal with the shortest path problem.

We define and study Euclidean and spatial network variants of a new path finding problem: given a set of safe zones, find paths that minimize the distance traveled outside the safe zones. In this problem, the entire space with the exception of the safe zones is unsafe, but passable, and it differs from problems that involve unsafe regions to be strictly avoided. As a result, existing algorithms are not effective solutions to the new problem.

In this paper, we consider a procedure for solving the shortest path problem in the Adleman-Lipton model. The procedure works in O(n) steps for the shortest path problem of an edge-weighted graph with n vertices.

Thek-Centrum Shortest Path Problem (kCSP[s, t]) is to minimize the sum of thek longest arcs in any (simple)s−t path containing at leastk arcs, wherek is a positive integer.kCSP is introduced and is shown to be NP-Hard, although it is polynomially solvable ifk is constrained to be no greater than the number of arcs in ans−t path with fewest arcs. Some properties of the problem are studied and a new weakly dual problem is also introduced.

We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the deviation of the weights, measured by the weighted l 1 norm or weighted l ∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree problem and the inverse maximum capacity path problem.

In this paper we generalize the classical shortest path problem in two ways. We consider two objective functions and time-dependent data. The resulting problem, called the time-dependent bicriteria shortest path problem (TdBiSP), has several interesting practical applications, but has not gained much attention in the literature. After reviewing relevant literature we develop a new algorithm for the TdBiSP with non-negative data. Numerical tests show the superiority of our algorithm compared with an existing algorithm in the literature. Furthermore, we discuss algorithms for the TdBiSP with negative travel times and costs.

We investigate the problem of how to evaluate efficiently a collection of shortest path queries on massive graphs that are too big to fit in the main memory. To evaluate a shortest path query efficiently, we introduce two pruning algorithms. These algorithms differ on the extent of materialization of shortest path cost and on how the search space is pruned. By grouping shortest path queries properly, batch processing improves the performance of shortest path query evaluation. Extensive study is also done on fragment sizes, cache sizes and query types that we show that affect the performance of a disk-based shortest path algorithm. The performance and scalability of proposed techniques are evaluated with large road systems in the Eastern United States. To demonstrate that the proposed disk-based algorithms are viable, we show that their search times are significant better than that of main-memory Dijkstra's algorithm.

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.

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a Min-Min problem. We prove that this problem is NP-complete in either single link cost (e.g., dedicated backup bandwidth) or dual link cost (e.g., shared backup bandwidth) networks. In addition, it is NP-hard to obtain a K-approximation to the optimal solution for any K > 1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the Min-Sum problem in an undirected network with ordered dual cost links (called the MSOD problem). To solve the Min-Min problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the Min-Min problem called COnflicting Link Exclusion (COLE), which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing integer linear programming (ILP)-based approaches but also achieves a good balance among the active path length, bandwidth efficiency, and recovery time.

The 2-terminal shortest path problem is to find a shortest path between two specified vertices in a given graph G. In this paper, we consider this problem in the following situation: G is given before the two vertices are specified so that some preprocessing is allowed to reduce the response time. We present a method for calculating lower bounds of the length of the shortest path for any pair of vertices. Experimental results show that the A* algorithm with our method performs much better than previous methods.

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.

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

In this paper, we study the shortest path problem with stochastic arc length. According to different decision criteria, we originally propose the concepts of expected shortest path, α-shortest path and the most shortest path, and present three new types of models: expected value model, chance-constrained programming and dependent-chance programming. In order to solve these models, a hybrid intelligent algorithm integrating stochastic simulation and genetic algorithm is developed and some numerical examples are given to illustrate its effectiveness.

We consider a variant of the constrained shortest path problem, where the constraints come from a set of forbidden paths (arc sequences) that cannot be part of any feasible solution. Two solution approaches are proposed for this variant. The first uses Aho and Corasick's keyword matching algorithm to filter paths produced by a k-shortest paths algorithm. The second generalizes Martins' deviation path approach for the k-shortest paths problem by merging the original graph with a state graph derived from Aho and Corasick's algorithm. Like Martins' approach, the second method amounts to a polynomial reduction of the shortest path problem with forbidden paths to a classic shortest path problem. Its significant advantage over the first approach is that it allows considering forbidden paths in more general shortest path problems such as the shortest path problem with resource constraints.

This paper presents two solution approaches for taking into account the displacement mode (forward or in reverse) of vehicles during the solution of the shortest path problem. In the first approach, a graph including all aspects of the problem is constructed and a classical shortest path algorithm is used to solve the problem. In the second approach, a more simple graph is constructed, and all the constraints of the problem are considered during the solution of the shortest path problem. This problem is important for routing a fleet of automated vehicles on a one-lane bidirectional graph.

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n2) time sequential algorithm and anO(n2/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.

The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.

This paper presents a computational method for finding the shortest path along polyhedral surfaces. This method is useful for verifying that there is a sufficient distance between two electrical components to prevent the occurrence of a spark between them in product design. We propose an extended algorithm based on the Kanai-Suzuki method, which finds an approximate shortest path by reducing the problem to searching the shortest path on the discrete weighted graph that corresponds to a polyhedral surface. The accuracy of the solution obtained by the Kanai-Suzuki method is occasionally insufficient for our requirements in product design. To achieve higher accuracy without increasing the computational cost drastically, we extend the algorithm by adopting two additional methods: “geometrical improvement” and the “K shortest path algorithm.” Geometrical improvement improves the local optimality by using the geometrical information around a path obtained by the graph method. The K shortest path algorithm, on the other hand, improves the global optimality by finding multiple initial paths for searching the shortest path. For some representative polyhedral surfaces we performed numerical experiments and demonstrated the effectiveness of the proposed method by comparing the shortest paths obtained by the Chen-Han exact method and the Kanai-Suzuki approximate method with the ones obtained by our method.

Algorithms are presented for external matrix multiplication and for all-pairs shortest path computation. In comparison with earlier algorithms, the amount of I/O is reduced by a constant factor. The all-pairs shortest path algorithm even performs fewer internal operations, making the algorithm practically interesting.

In a biconnected graph, a detour is the best alternative path from a detour-starting vertex to the destination vertex. A detour-starting vertex is the vertex from which the original shortest path is changed. The longest detour ( LD ) problem is to find a detour-critical edge in a shortest path such that the removal of the edge results in the maximum distance increment. In this paper, we deal with the LD problem with respect to a shortest path tree. An efficient algorithm which takes O ( mα ( m , n )) time for finding a detour-critical edge in a shortest path tree is proposed, where α is a functional inverse of Ackermann’s function.

Many real problems can be modelled as robust shortest path problems on interval digraphs, where intervals represent uncertainty about real costs and a robust path is not too far from the shortest path for each possible configuration of the arc costs. A branch and bound algorithm for this problem is presented.

In this paper, a version of the quickest path problem is considered in which arc capacities are fixed but lead times are expressed as intervals on real line. By considering order relations that represent the decision maker's preference between interval transmission times, we show that the problem can be solved by transforming it into a sequence of bicriteria shortest path problems in properly defined networks.

The multicriteria shortest path problem is considered. The paper presents the interactive method of analyzing this problem by the reference point approach. The reference point guided labeling algorithm was developed. This algorithm finds the Pareto-optimal shortest path which is best attuned to the specified preferences.

Shortest path algorithms are used for a large variety of optimisation problems in network and transportation analysis. They are also used in image analysis for object segmentation, disparity estimation, path finding and crack detection. Sometimes the topology of the problem demands that the path be circular. Such circular path constraints occur in polar object segmentation, disparity estimation for panoramic stereo images and in shortest paths around a cylinder. In this paper we present a new efficient algorithm for circular shortest path determination on a $u$-by-$v$ trellis in $O(u^{1.6} v)$ average time. We impose a binary search tree on the set of path endpoints and use a best-first Branch and Bound search technique to efficiently obtain the global minimum circular path. The typical running time of our circular shortest path algorithm on a 256$\times$256 image is in the order of 0.1 seconds on a 1GHz Dell P3 workstation under the Linux operating system. Applications to crack detection and object segmentation are presented.

In this paper we give bounds on the complexity of some algorithms for approximating 2-D and 3-D polygonal paths with the infinite beam measure of error. While the time/space complexities of the algorithms known for other error measures are well understood, path approximation with infinite beam measure seems to be harder due to the complexity of some geometric structures that arise in the known approaches. Our results answer some open problems left in previous work. We also present a more careful analysis of the time complexity of the general iterative algorithm for infinite beam measure and show that it could perform much better in practice than in the worst case. We then propose a new approach for path approximation that consists of a breadth first traversal of the path approximation graph, without constructing the graph. This approach can be applied to any error criterion in any constant dimension. The running time of the new algorithm depends on the size of the output: if the optimal approximating path has m vertices, the algorithm performs F(m) iterations rather than n–1 in the previous approaches, where F(m) \le n–1 is the number of vertices of the path approximation graph that can be reached with at most m–2 edges. This is the first output sensitive path approximation algorithm.

In the field of shortest path problems, many involve the application of a series of independent shortest path algorithms. In this paper we present a new framework for shortest path algorithm which exploits information from previous shortest path calculations. This framework enables the prioritizing of nodes with optimal distance labels (or minimum arrival time) to save the computation time. Different mechanisms to replenish the priority scan eligible list PSE are studied. Computer implementations and numerical results are presented.

One of the key issues in any quality-of-service (QoS) routing framework is how to compute a path that satisfies given QoS constraints. In this paper, we focus on the path computation problem subject to the bandwidth and delay constraints. This problem can be easily solved if the exact state information is available to the node performing the path computation function. In practice, however, nodes have only imprecise knowledge of the network state. The reliance on outdated information and treating this information as exact can significantly degrade the effectiveness of the path selection algorithm. To address this problem, we adopt a probabilistic approach in which the state parameters (available bandwidth and delay) are characterized by random variables. The goal is then to find the most-probable bandwidth-delay-constrained path (MP-BDCP). We provide efficient solutions for the MP-BDCP problem by decomposing it into two subproblems: the most-probable delay-constrained path (MP-DCP) problem and the most-probable bandwidth-constrained path (MP-BCP) problem. MP-DCP by itself is known to be NP-hard, necessitating the use of approximate solutions. By employing the central limit theorem and Lagrange relaxation techniques, we provide two complementary solutions for MP-DCP. These solutions are found to be highly efficient, requiring on average a few iterations of Dijkstra's shortest path algorithm. As for MP-BCP, it can be easily transformed into a variant of the shortest path problem. Our solutions for MP-DCP and MP-BCP are then combined to address the MP-BDCP problem by obtaining a set of near-nondominated paths. Decision makers can then select one or more of these paths based on a specific utility function. Extensive simulations are used to demonstrate the efficiency of the proposed algorithmic solutions and, more generally, to contrast the probabilistic path selection approach with the standard threshold-based triggered approach.

Shortest path algorithms have been used in a number of applications such as crack detection, road or linear feature extraction in images. There are applications where the starting and ending positions of the shortest path need to be constrained. In this paper, we present several new algorithms for the extraction of a circular shortest path in an image such that the starting and ending positions coincide. The new algorithms we developed include multiple search algorithm, image patching algorithm, multiple backtracking algorithm, the combination of image patching and multiple back-tracking algorithm, and approximate algorithm. The typical running time of our circular shortest path extraction algorithm on a 256×256 image is about 0.3 s on a rather slow 85 MHz Sun SPARC computer. A variety of real images for crack detection in borehole data and object boundary extraction have been tested and good results have been obtained.

Let G be a weighted graph with n vertices and m edges. We address the d-cycle problem, i.e., the problem of finding a subgraph of minimum weight with given cyclomatic number d. Hartvigsen [Minimum path bases, J. Algorithms 15 (1993) 125-142] presented an algorithm with running time O(n2m) and O(n2d-1m2) for the cyclomatic numbers d = 1 and d ≥ 2, respectively. Using a (d + 1)-shortest-paths algorithm, we develop a new more efficient algorithm for the d-cycle problem with running time O(n2d-1 + n2m + n3 log n).

The time-constrained shortest path problem is an important generalization of the shortest path problem. Recently, a model called traffic-light control model was introduced by Chen and Yang [Transport. Res. B 34 (2000) 241] to simulate the operations of traffic-light control in a city. The constraints of the model consist of a repeated sequence of time windows, and each window allows only certain routes to pass through a node. In this paper, we introduce a new kind of network called on–off time-switch network in which an arc is associated with a sequence of windows with status “on” or “off” analogous to “go” or “wait”. We show that both networks have the same mathematical structure in the sense that a path in one network corresponds to a path in the other one. Since Chen and Yang have developed algorithms to find the minimum total time path in the previous paper, we include one more criterion in this paper: weighted number of stops. To solve this bi-criteria path problem, we transform the traffic-light network into the on–off time-switch network, which allows us to take advantages of the special structure to design more efficient algorithms. By this transformation, finding the bi-criteria shortest path in the traffic-light network can be done in time O(#Wn3), where n is the number of nodes and #W is a given maximum number of weighted stops.

A fast path planning method by optimization of a path graph for both efficiency and accuracy is proposed. A conventional quadtree-based path planning approach is simple, robust, and efficient. However, it has two limitations. We propose a path graph optimization technique employing a compact mesh representation. A world space is triangulated into a base mesh and the base mesh is simplified to a compact mesh. The compact mesh representation is object-dependent; the positions of vertexes of the mesh are optimized according to the curvatures of the obstacles. The compact mesh represents the obstacles as accurately as the quadtree even though using much fewer vertexes than the quadtree. The compact mesh distributes vertexes in a free space in a balanced way by ensuring that the lengths of edges are below an edge length threshold. An optimized path graph is extracted from the compact mesh. An iterative vertex pushing method is proposed to include important obstacle boundary edges in the path graph. Dijkstra's shortest path searching algorithm is used to search the shortest path in the path graph. Experimental results show that the path planning using the optimized path graph is an order of magnitude faster than the quadtree approach while the length of the path generated by the proposed method is almost the same as that of the path generated by the quadtree.

In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a “virtual source”. We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n2), where n is the number of nodes. Numerical experiments are reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches.

Floyd Warshall‘s Algorithm is a simple and widely used algorithm to compute shortest path between all pairs of vertices in an edge weighted directed graph. It can also be used to detect the presence of negative cycles. Many researchers have given many other approaches for finding all pair shortest path but they reduced the complexity by using complex data structures. In this paper, we suggests a technique for finding shortest path based on Floyd Warshall‘s algorithm with reduced time complexity and also by not using complex data structures. We present an O(n

finding the shortest path over network is very difficult and it is the target for much research, after many researches get the result in many of algorithm and many a mount based on the performance for these algorithm .Shortest paths problems are familiar problems in computer science and mathematics. In these problems, edge weights may represent distances, costs, or any other real-valued quantity that can be added along a path, and that one may wish to minimize. Thus, edge weights are real numbers and the specific operations used are addition to compute the weight of a path and minimum to select the best path weight. In this paper we use the Dijkstra's algorithm with new technique to find the shortest path over network to reduce the time we need to find the best path, in this paper we use node for network with the same value which can be use it to find the shortest path but this depend on the number of transition for every node when the node have high number then the node have the high priority to choose it by using this method we descries the time to find the short path .to make this algorithm more distinguish apply multi-agent system ( Automata with multiplicities ) to find the short path.

As a mathematical model for the passenger routing problem for ticketing in a railway network, we consider a shortest path problem for a directed graph with edges labeled with a cost and a capacity. The problem is to push flow f from a specified source to all other vertices with the minimum cost for all f values. If there are t different capacity values, we can solve the single source shortest path problem for all ft times in $$Otm+tn\log n=Om^2$$Otm+tnlogn=Om2 time when $$t=m$$t=m. We improve this time to Ocmn if edge costs are non-negative integers bounded by c.

The maximum probability shortest path problem involves the constrained shortest path problem in a given graph where the arcs resources are independent normally distributed random variables. We maximize the probability that all resource constraints are jointly satisfied while the path cost does not exceed a given threshold. We use a second-order cone programming approximation for solving the continuous relaxation problem. In order to solve this stochastic combinatorial problem, a branch-and-bound algorithm is proposed, and numerical examples on randomly generated instances are given.

We examine the evolution of the best choice algorithm and the probability of its success from a directed path to the linear order of the same cardinality through $k$th powers of a directed path, $1 \leq k < n$. The vertices of a $k$th power of a directed path of a known length $n$ are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already come. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). It is shown that the probability of success $p_n$ for the optimal algorithm for the $k$th power of a directed path satisfies $p_n = \Theta(n^{-1/(k+1)})$. We also consider the case when the selector knows the distance in the underlying path between each two vertices that are joined by an edge in the induced graph. An optimal algorithm for this choice problem is presented. The exact probability of success when using this algorithm is given.

International audience; Finding the shortest path in a directed graph is one of the most important combinatorial optimization problems, having applications in a wide range of fields. In its basic version, however, the problem fails to represent situations in which the value of the objective function is determined not only by the choice of each single arc, but also by the combined presence of pairs of arcs in the solution. In this paper we model these situations as a Quadratic Shortest Path Problem, which calls for the minimization of a quadratic objective function subject to shortest-path constraints. We prove strong NP-hardness of the problem and analyze polynomially solvable special cases, obtained by restricting the distance of arc pairs in the graph that appear jointly in a quadratic monomial of the objective function. Based on this special case and problem structure, we devise fast lower bounding procedures for the general problem and show computationally that they clearly outperform other approaches proposed in the literature in terms of its strength.

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. 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 on general graphs; a 2-approximation, a 3-approximation, and an 8-approximation for the MESP-problem can be computed in \(\mathcal {O}(n^3)\) time, in \(\mathcal {O}(nm)\) time, and in linear time, respectively; a shortest path of minimum eccentricity k in general graphs can be computed in \(\mathcal {O}(n^{2k+2}m)\) time; the MESP-problem can be solved in linear time for trees.

The shortest path problem is a classical problem in graph theory, it is also one of the classical problems in the field of combinatorial optimization. This paper analyzes the basic harmony search algorithm model, and points out its insufficiency in solving the shortest path problem, then modifies the harmony memory and perturbation method. The simulation experiment shows that the improved harmony search algorithm (IHSA) has faster global convergence speed, and can obtain more accurate optimal path. IHSA is an effective solution to solve the shortest path problem. Keywords: multi-objective bi-level programming, genetic algorithm, interpolation.

A minimum Hamiltonian completion of a graph G is a minimum-size set of edges that, when added to G, guarantee a Hamiltonian path. Finding a Hamiltonian completion has applications to frequency assignment as well as distributed computing. If the new edges are deleted from the Hamiltonian path, one is left with a minimum path cover, a minimum-size set of vertex-disjoint paths that cover the vertices of G. For arbitrary graphs, constructing a minimum Hamiltonian completion or path cover is clearly NP-hard, but there exists a linear-time algorithm for trees. In this paper we first give a description and proof of correctness for this linear-time algorithm that is simpler and more intuitive than those given previously. We show that the algorithm extends also to unicyclic graphs. We then give a new method for finding an optimal path cover or Hamiltonian completion for a tree that uses a reduction to a maximum flow problem. In addition, we show how to extend the reduction to construct, if possible, a covering of the vertices of a bipartite graph with vertex-disjoint cycles, that is, a 2-factor.

The shortest-paths problem is an important problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The Shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one node to another often gives the best way to route message between the nodes. This paper presents an O(n2) time algorithm for solving all pairs shortest path problems on trapezoid graphs which are extensions of interval graphs and permutation graphs. The space complexity of this algorithm is of O(n2). This problem has been solved by constructing n breadth-first search (BFS) trees with each of the n vertices as root. As the lower bound of time complexity for computing the all pairs shortest paths is known to be of O(n2), this proposed algorithm is optimal.