K.H. Tsai, Ran Ma · 2003
In considering distributed adaptive routing schemes for large networks with dynamic topology, the need for an unconventional shortest path algorithm arises from the excessive computation overhead associated with repeated path/distance calculations. The authors provide the design specifics of such an algorithm, and establish its performance characteristics through rigorous analysis and simulation. The new algorithm exploits the intrinsic parallelism of neural network architectures and solves the single-pair shortest path problem in such a way that: (i) the computation time is independent of the number of network nodes; and (ii) the frequent shortest distance/path re-calculations inherently associated with topology changes are performed much faster than conventional algorithms. Simple exploitation of the inherent parallelism allows extension of the algorithm to solving single-source and all-pair shortest path problems without compromising the trait of constant convergent complexity.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 0
Yoichi Iwata, Yutaro Yamaguchi · arXiv (Cornell University) · 2019
We study a constrained shortest path problem in group-labeled graphs with nonnegative edge length, called the shortest non-zero path problem. Depending on the group in question, this problem includes two types of tractable variants in undirected graphs: one is the parity-constrained shortest path/cycle problem, and the other is computing a shortest noncontractible cycle in surface-embedded graphs. For the shortest non-zero path problem with respect to finite abelian groups, Kobayashi and Toyooka (2017) proposed a randomized, pseudopolynomial-time algorithm via permanent computation. For a slightly more general class of groups, Yamaguchi (2016) showed a reduction of the problem to the weighted linear matroid parity problem. In particular, some cases are solved in strongly polynomial time via the reduction with the aid of a deterministic, polynomial-time algorithm for the weighted linear matroid parity problem developed by Iwata and Kobayashi (2021), which generalizes a well-known fact that the parity-constrained shortest path problem is solved via weighted matching. In this paper, as the first general solution independent of the group, we present a rather simple, deterministic, and strongly polynomial-time algorithm for the shortest non-zero path problem. The algorithm is based on Dijkstra's algorithm for the unconstrained shortest path problem and Edmonds' blossom shrinking technique in matching algorithms; this approach is inspired by Derigs' faster algorithm (1985) for the parity-constrained shortest path problem via a reduction to weighted matching. Furthermore, we improve our algorithm so that it does not require explicit blossom shrinking, and make the computational time match Derigs' one. In the speeding-up step, a dual linear programming formulation of the equivalent problem based on potential maximization for the unconstrained shortest path problem plays a key role.
Cited by 0Open access
D.I. Lawson · 2002
A method of finding the shortest concurrent path on a graph for p concurrent players, p/spl ges/1, is presented. Real-time applications, the routing of aircraft and the scheduling of collections of tasks are then discussed and a parallel Bellman shortest path algorithm is described which finds the shortest path from node r to node s on a graph G. Using this algorithm and the proper configuration of processors the shortest path on a graph with k nodes can be found in O(log n) time for 2(m/sup -1/)+1<k<(n=2/sup m/)+1. This is faster than other algorithms currently available within the professional literature. To find concurrent paths is a new problem which has particular application for the best use of resources. The algorithm can be adapted to schedule a wide variety of concurrent tasks.
Cited by 2
Eranda Çela, Bettina Klinz, Stefan Lendl et al. · arXiv (Cornell University) · 2023
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.
Cited by 1Open access
Eranda Çela, Bettina Klinz, Stefan Lendl et al. · Mathematical Programming · 2024
An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best algorithm. The algorithm is based on a new insight revealing that the linearizability of the QSPP for acyclic digraphs can be seen as a local property. Our approach extends to the more general higher-order shortest path problem.
Cited by 2Open access
Tripathy, Alok · SMARTech Repository (Georgia Institute of Technology) · 2019
Point-to-point shortest path (PPSP), or s-t connectivity, is a\nvariant of the shortest path problem found in graph theory. In\nthis problem, we are given a graph and pairs of vertices over\ntime, and the output is the shortest path between each pair\nof vertices. In this paper, we present two algorithms. Our first\nalgorithm approximately solves the PPSP problem on any\narbitrary graph. For each pair of vertices queried, it accurately\nand efficiently estimates the shortest path between the two\nvertices. Our second algorithm extends the first to work on\ndynamic graphs. That is, our second algorithm can efficiently\naccount for changes in the graph, such as friend requests\non the Facebook network or road closures on road networks.\nAt a high level, both algorithms partition the graph into\nhighly connected communities. To respond to a query q(u, v),\nthey each find the fewest number of partitions between u\nand v, and the shortest path through each partition. We\nshow that our static graph algorithm can approximate the\ndistance between two vertices with about 20% − 35% percent\nerror and anywhere from 80X − 70000X faster than a BFS\nin practice with the right choice of partitions. Additionally,\nwe show that our dynamic graph algorithm can account for\nupdates to the graph anywhere from 20X − 20000X faster\nthan rerunning the static graph algorithm for each change to\nthe graph.
Cited by 0
Sameer Alani, Atheer Baseel, Mustafa Maad Hamdi, Sami Abduljabbar Rashid · Bulletin of Miscellaneous Information (Royal Gardens Kew) · 2020
In the single-source shortest path (SSSP) problem, the shortest paths from a source vertex v to all other vertices in a graph should be executed in the best way. A common algorithm to solve the (SSSP) is the A* and Ant colony optimization (ACO). However, the traditional A* is fast but not accurate because it does not calculate all node’s distance of the graph. Moreover, it is slow in path computation. In this paper, we propose a new technique that consists of a hybridizing of A* algorithm and ant colony optimization (ACO). This solution depends on applying the optimization on the best path. For justification, the proposed algorithm has been applied to the parking system as a case study to validate the proposed algorithm performance. First, A*algorithm generates the shortest path in faster time complexity. ACO will optimize this path and output the best path. The result showed that the proposed solution provides an average decreasing time complexity e is 13.5%.
Cited by 0Open access
Arthur Astakhov, Lyudmila Chernenkaia · 2025
The application of shortest path algorithms remains relevant despite the historical bulkiness of these approaches. This topic is also related to the need to not only consider the computational complexity of algorithms as theoretical aspects of time based on the traversal of vertices and edges, but also practical estimation of the running time of the software implementing the algorithm. This study describes the proposed graph clustering method for application in the problem of finding the shortest path and increasing the speed of the Bellman-Ford algorithm by reducing the set of considered vertices. The mathematical formalization of the graph clustering method is described, including the steps of the algorithm operation under the conditions of the modified graph utilization method, the unconditionality of such an approach in the process of use in the shortest path search problem is evaluated. The effectiveness of the proposed graph clustering method for reducing the execution time of the Bellman-Ford algorithm due to the reduction of the considered vertices in the graph is analyzed. A software implementation is proposed to perform graph clustering for further use in the shortest path search method based on the Bellman-Ford algorithm. An experiment is also conducted to compare the speed of performing the shortest path search by the Bellman-Ford algorithm under different graph utilization approaches, which results that the graph clustering method is 75% faster than the classical algorithm and also faster than the maximum distance constraint method obtained by restricting the area of the considered vertices by 38.89%.
Cited by 0
W. Matthew Carlyle, R. Kevin Wood · 2003
Recently published research indicates that a vertex-labeling algorithm based on dynamic-programming concepts is the most efficient procedure available for solving constrained shortest-path problems (CSPPs), i.e., shortest-path problems with one or more side constraints on the total “weight ” of the optimal path. However, we investigate an alternative procedure that Lagrangianises the side constraints, optimises the resulting Lagrangian function and then closes any duality gap through enumeration of near-shortest paths. These paths are measured with respect to Lagrangian-modified edge lengths, and “near-shortest ” implies ɛ-optimal, with ɛ equal to the duality gap. Our recently developed procedure for enumerating nearshortest-paths leads to an algorithm for CSPP that, empirically, proves to be an order of magnitude faster than the most recent vertex-labeling algorithm. 1
Cited by 0
Ali Khatami Firoozabadi, Hossein Mohebbi, Mohammad Zarei Mahmoodabadi · SHILAP Revista de lepidopterología · 2011
Shortest-path problem is one of the well-known optimization problems that has been studied by many scientists in recent years. Applications of this problem such as transportation and communication are generally solved by Dijkstra's Algorithm (Labeling). In this paper, two separate scientific fields, electronics and operation research have been linked to each other and a new algorithm has been created for to find the optimization solution of a shortest- path problem by using electric networks and rules. The proposed algorithm can solve the shortest-path problem in directed graphs and no order ones, and also can solve the longest path problems in directed graphs. In this algorithm, electrical network are used in a way that the resistance value of each branch is equal to each edge weights in the shortest-path problems. Then with using Ohm Law and Kirchhaffs Voltage Law (KVL), the current in each circuit cycle is calculated. Then the branches that contain the most passing current are specified, and according to Ohm’s Law, has the lowest resistance or weight. Thus, the shortest path in the network is achieved. Advantage of this algorithm is faster convergence to the answer and less computing time than the conventional method, especially in networks with more nods. The mentioned algorithm has been described for three examples.
Cited by 0Open access
Juan Li · Advanced materials research · 2014
The traditional evolutionary algorithm is cannot converge faster to solve the path optimization problems, and the path that is computed is not the shortest path, in allusion to the disadvantage of this algorithm, a mutation particle swarm optimization algorithm is proposed. The algorithm introduces the adaptive mutation strategy, and accelerated the speed to search for the global optimal solution. For seven examples experiment in standard database, the result shows that the algorithm is more efficient..
Cited by 2Open access
Udit Agarwal, Vijaya Ramachandran · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
We present algorithms and techniques for several problems related to finding multiple simple shortest paths and cycles in a graph. Our main result is a new algorithm for finding k simple shortest paths for all pairs of vertices in a weighted directed graph G = (V, E). For k = 2 our algorithm runs in O(mn + n^2 log n) time where m and n are the number of edges and vertices in G. For k = 3 our algorithm runs in O(mn^2 + n^3 log n) time, which is almost a factor of n faster than the best previous algorithm. Our approach is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in most of the prior work on simple shortest paths, replacement paths, and distance sensitivity oracles. We present new algorithms for generating simple cycles and simple paths in G in non-decreasing order of their weight. The algorithm for generating simple paths is much faster,and uses another variant of path extensions.
Cited by 5Open access
W. Matthew Carlyle, Johannes O. Royset, R. Kevin Wood · 2003
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian func-tion, identifies a feasible solution, and then closes any optimality gap by enumerating near-shortest paths, measured with respect to the Lagrangianized length. “Near-shortest ” implies -optimal, with a varying that equals the current optimality gap. The algorithm exploits a new path-enumeration method, aggregate constraints, preprocessing to eliminate edges that cannot form part of an optimal solution, “reprocessing ” that reapplies preprocessing steps as improved solutions are found and, when needed, a “phase-I procedure ” to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art label-setting algorithm on singly constrained randomly-generated grid networks. On multi-constrained grid networks, road networks, and networks for aircraft routing the advantage varies, but, overall, the new algorithm is competitive with the label-setting algorithm. 1
Cited by 0
W. Matthew Carlyle, Johannes O. Royset, R. Kevin Wood · 2008
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian func-tion, identifies a feasible solution, and then closes any optimality gap by enumerating near-shortest paths, measured with respect to the Lagrangianized length. “Near-shortest ” implies -optimal, with a varying that equals the current optimality gap. The algorithm exploits a new path-enumeration method, aggregate constraints, preprocessing to eliminate edges that cannot form part of an optimal solution, “reprocessing ” that reapplies preprocessing steps as improved solutions are found and, when needed, a “phase-I procedure ” to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art label-setting algorithm on singly constrained randomly-generated grid networks. On multi-constrained grid networks, road networks, and networks for aircraft routing the advantage varies, but, overall, the new algorithm is competitive with the label-setting algorithm. 1
Cited by 0
Carlyle W. Matthew, W. Matthew Carlyle, Johannes O. Royset et al. · 2007
The constrained shortest-path problem (CSPP) generalizes the standard shortest-path problem by adding one or more path-weight side constraints. We present a new algorithm for CSPP that Lagrangianizes those constraints, optimizes the resulting Lagrangian func-tion, identifies a feasible solution, and then closes any optimality gap by enumerating near-shortest paths, measured with respect to the Lagrangianized length. “Near-shortest ” implies -optimal, with a varying that equals the current optimality gap. The algorithm exploits a new path-enumeration method, aggregate constraints, preprocessing to eliminate edges that cannot form part of an optimal solution, “reprocessing ” that reapplies preprocessing steps as improved solutions are found and, when needed, a “phase-I procedure ” to identify a feasible solution before searching for an optimal one. The new algorithm is often an order of magnitude faster than a state-of-the-art label-setting algorithm on singly constrained randomly-generated grid networks. On multi-constrained grid networks, road networks, and networks for aircraft routing the advantage varies, but, overall, the new algorithm is competitive with the label-setting algorithm. 1
Cited by 0
Guy Desaulniers, François Soumis · PolyPublie (École Polytechnique de Montréal) · 1993
We study the problem of finding a shortest path for a car-like mobile robot with a minimal turning radius constraint. This vehicle can move either forward or backward in an unconstrained environment. By applying necessary conditions on the segment lengths of shortest paths, we partition the configuration space into elements such that a single path type is associated with 150 elements and two path types are associated with the other 11 elements. A shortest path from a fixed initial configuration to any final configuration in an element can always be found among the paths of types associated with that element. We then present an algorithm based on this partition and we give results showing that our algorithm is 15 times faster on average than the Reeds-Shepp algorithm (1990).
Cited by 1
Inun, Haidie · UTHM Institutional Repository (Universiti Tun Hussein Onn Malaysia) · 2013
The purpose of this study is to develop an efficient offline path planning algorithm that is capable of finding optimal collision-free paths from a starting point to a goal point. The algorithm is based on Voronoi diagram method for the environment representation combined with Dijkstra’s algorithm to find the shortest path. Since Voronoi diagram path exhibits sharp corners and redundant turns, path tracking was applied considering the robot’s kinematic constraints. The results has shown that the Voronoi diagram path planning method recorded fast computational time as it provides simpler, faster and efficient path finding. The final path, after considering robot’s kinematic constraints, provides shorter path length and smoother compared to the original one. The final path can be tuned to the desired path by tuning the parameter setting; velocity, v and minimum turning radius, Rmin. In comparison with the Cell Decomposition method, it shows that Voronoi diagram has a faster computation time. This leads to the reduced cost in terms of time. The findings of this research have shown that Voronoi Diagram and Dijkstra’s Algorithm are a good combination in the path planning problem in terms of finding a safe and shortest path.
Cited by 0Open access
Poetri Hana Nurhandayani, Wamiliana Wamiliana, Misgiyati Misgiyati et al. · Explore Jurnal Sistem informasi dan telematika · 2024
Determining the shortest path between one location to another location is one of the problems that usually has to be faced in daily life. The shortest path will affect the shorter time needed, less money used, and others. In this study, we will discuss the comparison of Dijsktra’s Algorithm and Floyd Warshal’s Algorithm to determine the shortest path of the biggest and the most famous traditional market in Bandar Lampung City, which is Bambu Kuning traditional market, to 26 other traditional markets in Bandar Lampung city. The Phyton programming language is used to implement both algorithms on the data of 27 traditional markets. The results show that both algorithms give the same solution. However, the processing time of Dijsktra’s Algorithm (0.1063 seconds) is faster than Floyd Warshal’s algorithm (0.1691 seconds)
Cited by 0Open access
Yunpeng Li · arXiv (Cornell University) · 2014
The single-source shortest path problem is a classical problem in the research field of graph algorithm. In this paper, a new single-source shortest path algorithm for nonnegative weight graph is proposed. The algorithm can compress multi-round Fibonacci heap operations to one round to save running time relative to Dijkstra's algorithm using Fibonacci heap. The time complexity of the algorithm is also O(m+nlogn) in the worst case, where m is the number of edges and n is the number of nodes. However, the bound can be linear in some case, for example, when edge weights of a graph are all the same and the hop count of the longest shortest path is much less than n.Based on the theoretical analyses, we demonstrate that the algorithm is faster than Dijkstra's algorithm using Fibonacci heap in average situation when n is large enough.
Cited by 0Open access
Chan, Chor Cheng · DR-NTU (Nanyang Technological University) · 2023
Given the increasing emphasis on developing autonomous vehicles, it is of value to continuously improve the path planning aspect which is considered a key of the autonomy of autonomous vehicles. Considering the path planning problem of determining the shortest path a forward-moving vehicle can take between 2 points with initial and terminal directions in a 2-dimensional plane, the classical solution of Dubins paths where the paths can be classified into 6 different path types was developed. Widespread applications of utilising the shortest Dubins paths has sparked the need for an algorithm that is faster than exhaustively determining the shortest Dubins path and that can be generalised for any points and directions in the 2-dimensional plane. Hence, this paper seeks to implement a hybrid algorithm that combines a classification method and the exhaustive method, alongside studying the computational cost of normalisation for generalisation before using the hybrid algorithm. The accuracy of the hybrid algorithm in determining the shortest Dubins path was verified with test cases developed to achieve optimal decision coverage. The performance of the hybrid algorithm was measured and pitted against the exhaustive method, where the hybrid algorithm performed better overall. The computational cost of normalisation was relatively larger when paired with the hybrid algorithm than that of the exhaustive method.
Cited by 0