14 results on '"Shortest path problem"'
Search Results
2. Calculation of Fuzzy shortest path problem using Multi-valued Neutrosophic number under fuzzy environment.
- Author
-
Raut, Prasanta Kumar, Behera, Siva Prasad, Broumi, Said, and Mishra, Debdas
- Subjects
- *
GRAPH theory , *GRAPH connectivity , *FIRE stations , *TELECOMMUNICATION systems , *SERVICE stations , *FUZZY numbers - Abstract
The most well-known subject in graph theory is the shortest path problem (SPP), which has real-world applications in several different fields of study, including transportation, emergency services, network communications, fire station services, etc. The arc weights of the applicable SP problems are typically represented by fuzzy numbers in real-world applications. In this paper, we discussed the process of finding the shortest distance in a connected graph network in which the arc weights are multi-valued neutrosophic numbers (MNNs). Moreover, here we compare our method with some of the existing results and illustrate one implementation of our method with the help of one numerical example. [ABSTRACT FROM AUTHOR]
- Published
- 2023
3. On the shortest path problem of uncertain random digraphs.
- Author
-
Li, Hao and Zhang, Kun
- Subjects
- *
GRAPH theory , *ALGORITHMS , *RANDOM measures - Abstract
In the field of graph theory, the shortest path problem is one of the most significant problems. However, since varieties of indeterminated factors appear in complex networks, determining of the shortest path from one vertex to another in complex networks may be a lot more complicated than the cases in deterministic networks. To illustrate this problem, the model of uncertain random digraph will be proposed via chance theory, in which some arcs exist with degrees in probability measure and others exist with degrees in uncertain measure. The main focus of this paper is to investigate the main properties of the shortest path in uncertain random digraph. Methods and algorithms are designed to calculate the distribution of shortest path more efficiently. Besides, some numerical examples are presented to show the efficiency of these methods and algorithms. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
4. The k-interchange-constrained diameter of a transit network: a connectedness indicator that accounts for travel convenience.
- Author
-
Dehouche, Nassim
- Subjects
- *
DIAMETER , *MATHEMATICAL connectedness , *NP-hard problems , *GRAPH theory , *COMPUTATIONAL complexity , *INTEGERS - Abstract
We study two variants of the shortest path problem. Given an integer k , the k -color-constrained and the k -interchange-constrained shortest path problems, respectively, seek a shortest path that uses no more than k colors and one that makes no more than k − 1 alternations of colors. We show that the former problem is NP-hard, when the latter is tractable. The study of these problems is motivated by some limitations in the use of diameter-based metrics to evaluate the topological structure of transit networks. We notably show that indicators such as the diameter or directness of a transit network fail to adequately account for travel convenience in measuring the connectivity of a network and propose a new network indicator, based on solving the k -interchange-constrained shortest path problem, that aims at alleviating these limitations. [ABSTRACT FROM AUTHOR]
- Published
- 2020
- Full Text
- View/download PDF
5. The Shortest Path Problem for the Distant Graph of the Projective Line Over the Ring of Integers.
- Author
-
Matraś, Andrzej and Siemaszko, Artur
- Subjects
- *
RINGS of integers , *GRAPH theory , *PROBLEM solving , *CONTINUED fractions , *EUCLIDEAN geometry - Abstract
The distant graph $$G=G({\mathbb {P}}(Z), \vartriangle )$$ of the projective line over the ring of integers is considered. The shortest path problem in this graph is solved by use of Klein's geometric interpretation of Euclidean continued fractions. In case the minimal path is non-unique, all the possible splitting are described which allows us to give necessary and sufficient conditions for existence of a unique shortest path. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
6. On the Shortest Path Game.
- Author
-
Darmann, Andreas, Pferschy, Ulrich, and Schauer, Joachim
- Subjects
- *
GRAPH theory , *DECISION making , *POLYNOMIAL time algorithms , *ACYCLIC model , *DYNAMIC programming - Abstract
In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form. We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography . On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
7. Benchmarking a recurrent neural network based efficient shortest path problem (SPP) solver concept under difficult dynamic parameter settings conditions.
- Author
-
Chedjou, Jean Chamberlain and Kyamakya, Kyandoghere
- Subjects
- *
NEURAL computers , *PARAMETER estimation , *ORDINARY differential equations , *ARTIFICIAL neural networks , *GRAPH theory - Abstract
This paper develops for the first time an analytical approach inspired from the basic differential multiplier method (BDMM) in a framework concept involving coupled nonlinear ordinary differential equations (ODEs) for finding shortest path (SP) in dynamically reconfigurable graphs. The application of BDMM to the shortest-path problem (SPP) results into a set of coupled ODEs which do essentially describe/constitute a Recurrent Neural Network (RNN) model. This model is characterized by three fundamental parameters describing (or expressing) the following: (a) the graph topology (through the ‘incidence matrix’), (b) the edge weights (dynamic external weights setting capability), and (c) the dynamic re-configurability through external input(s) of the source–destination nodes pair. The coupled ODEs constitute a universal modeling framework for SP detection. The three fundamental parameters of this framework are valid for all types of graphs (directed, undirected, connected, non-connected, complete- and non-complete) regardless of their topology, magnitude, size, etc. An overall thorough methodology and an illustrative extensive evaluation are provided. It is noticed and demonstrated that the main advantage of the concept suggested is that arc costs, the origin–destination ( s–t ) pair setting, and the graph topology are external commands representing the inputs (and also the coefficients/parameters) of the ODE-processor model (RNN). This enables a high flexibility and a full re-configurability of the developed shortest path problem solver concept and thereby without any re-training need. Further, this RNN based SP solver concept can handle even graphs with negative arc weights as well as graphs with nonlinear path cost models. To stress test this new RNN shortest path problem solver concept, a benchmarking is performed, whereby a detailed comparison of its performance with one of the currently best amongst the related traditional neural network based concepts (i.e. the Dynamic Neural Network (DNN) based SP solver) is performed. The superiority of the novel RNN SPP solver is convincingly demonstrated in an extensive benchmark while considering computational efficiency, robustness, convergence, flexibility, and re-configurability as performance metrics. Finally, it is demonstrated that the concept developed is applicable to solving shortest path tree (SPT) problems. A case study (SPT) is considered and various results obtained using the concept developed are compared with the results provided by several algorithms namely the semi-dynamic Dijkstra algorithms, the semi-dynamic MBallString algorithms, and the fully-dynamic MFP algorithm. The efficiency of the concept developed for solving SPT problems in both static and dynamically reconfigurable graphs networks is clearly demonstrated through multiple application examples. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
8. Shortest Paths with Higher-Order Regularization.
- Author
-
Ulen, Johannes, Strandmark, Petter, and Kahl, Fredrik
- Subjects
- *
MATHEMATICAL regularization , *GRAPH theory , *DISCRETIZATION methods , *MATHEMATICAL optimization , *TORSION theory (Algebra) - Abstract
This paper describes a new method of finding thin, elongated structures in images and volumes. We use shortest paths to minimize very general functionals of higher-order curve properties, such as curvature and torsion. Our method uses line graphs to find the optimal path on a given discretization, often in the order of seconds on a single computer. The curves are then refined using local optimization making it possible to recover very smooth curves. We are able to place constraints on our curves such as maximum integrated curvature, or a maximum curvature at any point of the curve. To our knowledge, we are the first to perform experiments in three dimensions with curvature and torsion regularization. The largest graphs we process have over a hundred billion arcs. Experiments on medical images and in multi-view reconstruction show the significance and practical usefulness of higher order regularization. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
9. Model and algorithm for 4PLRP with uncertain delivery time.
- Author
-
Huang, Min, Ren, Liang, Lee, Loo Hay, Wang, Xingwei, Kuang, Hanbin, and Shi, Haibo
- Subjects
- *
MATHEMATICAL models , *GENETIC algorithms , *DECISION theory , *UNCERTAINTY (Information theory) , *ROUTING (Computer network management) , *GRAPH theory - Abstract
To address the challenge of logistics routing decision under uncertain environment, this paper studies a fourth party logistics routing problem (4PLRP) with uncertain delivery time (4PLRPU). A novel 4PLRPU model based on uncertainty theory is proposed by describing the delivery time of a third party logistics (3PL) provider as an uncertain variable. After that, the model is transformed into an equivalent deterministic model, and several improved genetic algorithms are designed to get solutions. To handle the problem of infeasible solutions in the proposed 4PLRPU, an improved node-based genetic algorithm (INGA) and an improved distance-based genetic algorithm (IDGA) are developed to reduce the computing time required to repair infeasible solutions, and an improved genetic algorithm based on the simple graph and Dijkstra algorithm (SDGA) is proposed to avoid the generation of infeasible solutions. Numerical experiments are conducted to investigate the performance of the proposed algorithms and verify the effectiveness of the proposed 4PLRPU model. The results show that INGA and SDGA are more effective than the standard genetic algorithm and IDGA at solving large-scale problems. Additionally, compared with the expected value model, the 4PLRPU model is more robust. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF
10. Dijkstra's algorithm and L-concave function maximization.
- Author
-
Murota, Kazuo and Shioura, Akiyoshi
- Subjects
- *
COMPUTER algorithms , *CONCAVE functions , *DIRECTED graphs , *GRAPH theory , *COMPUTATIONAL mathematics , *LINEAR programming - Abstract
Dijkstra's algorithm is a well-known algorithm for the single-source shortest path problem in a directed graph with nonnegative edge length. We discuss Dijkstra's algorithm from the viewpoint of discrete convex analysis, where the concept of discrete convexity called L-convexity plays a central role. We observe first that the dual of the linear programming (LP) formulation of the shortest path problem can be seen as a special case of L-concave function maximization. We then point out that the steepest ascent algorithm for L-concave function maximization, when applied to the LP dual of the shortest path problem and implemented with some auxiliary variables, coincides exactly with Dijkstra's algorithm. [ABSTRACT FROM AUTHOR]
- Published
- 2014
- Full Text
- View/download PDF
11. Node Early-Fixing: A Practical Speedup Technique for A* Algorithms.
- Author
-
Liang Zhao and Mingji Gao
- Subjects
- *
COMPUTER algorithms , *GRAPH theory , *NONNEGATIVE matrices , *PATH analysis (Statistics) , *COMPUTER network architectures - Abstract
Given a graph G with nonnegative edge lengths, a source vertex s and a destination vertex d, the Point-to-Point Shortest Path Problem asks to find a shortest path from s to d. For this problem, A* is a popular framework of practical algorithms, including the well-known Dijkstra's algorithm (1959), a recent ALT algorithm (Goldberg and Harrelson, SODA'05) and others. This paper presents a practical speed-up technique Node Early-Fixing for A* algorithms. Experiments with real networks show that it can speedup the calculation by efficiently reduce the number of unnecessary updates of distance labels in practice. [ABSTRACT FROM AUTHOR]
- Published
- 2013
- Full Text
- View/download PDF
12. An extended shortest path problem: A data envelopment analysis approach
- Author
-
Amirteimoori, Alireza
- Subjects
- *
GRAPH theory , *COMBINATORICS , *PATHS & cycles in graph theory , *DATA envelopment analysis , *LINEAR programming , *COST analysis , *MATHEMATICAL analysis - Abstract
Abstract: A special and important network structured linear programming problem is the shortest path problem. Classical shortest path problems assume that there are unit of shipping cost or profit along an arc. In many real occasions, various attributes (various costs and profits) are usually considered in a shortest path problem. Because of the frequent occurrence of such network structured problems, there is a need to develop an efficient procedure for handling these problems. This paper studies the shortest path problem in the case that multiple attributes are considered along the arcs. The concept of relative efficiency is defined for each path from initial node to final node. Then, an efficient path with the maximum efficiency is determined. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
13. Hierarchical Motion Planning With Dynamical Feasibility Guarantees for Mobile Robotic Vehicles.
- Author
-
Cowlagi, Raghvendra V. and Tsiotras, Panagiotis
- Subjects
- *
MOBILE robots , *PATHS & cycles in graph theory , *PROBLEM solving , *GRAPH theory , *COMPUTER algorithms , *FEASIBILITY studies - Abstract
Motion planning for mobile vehicles involves the solution of two disparate subproblems: the satisfaction of high-level logical task specifications and the design of low-level vehicle control laws. A hierarchical solution of these two subproblems is efficient, but it may not ensure compatibility between the high-level planner and the constraints that are imposed by the vehicle dynamics. To guarantee such compatibility, we propose a motion-planning framework that is based on a special interaction between these two levels of planning. In particular, we solve a special shortest path problem on a graph at a higher level of planning, and we use a lower level planner to determine the costs of the paths in that graph. The overall approach hinges on two novel ingredients: a graph-search algorithm that operates on sequences of vertices and a lower level planner that ensures consistency between the two levels of hierarchy by providing meaningful costs for the edge transitions of a higher level planner using dynamically feasible, collision-free trajectories. [ABSTRACT FROM PUBLISHER]
- Published
- 2012
- Full Text
- View/download PDF
14. Multi-dimensional labelling approaches to solve the linear fractional elementary shortest path problem with time windows.
- Author
-
Guerriero, F. and Di Puglia Pugliese, L.
- Subjects
- *
GRAPH labelings , *GRAPH theory , *DIRECTED graphs , *FRACTIONAL integrals , *MATHEMATICAL analysis , *ALGORITHMS , *PATH analysis (Statistics) - Abstract
This paper investigates the linear fractional shortest path problem with time windows. For the specific problem, an elementary path with a minimum cost/time ratio is sought in a directed graph, where two parameters (i.e. cost and time) are associated with each arc and a time window is associated with each node. Indeed, a valid path must satisfy the time window constraints, which are assumed to be of the hard type. Multi-dimensional labelling algorithms are proposed to solve this variant of the classical shortest path problem. Extensive computational tests are carried out on a meaningful number of test problems, with the goal of assessing the behaviour of the proposed approaches. The computational study shows that the introduction of dominance rules and the adoption of a bi-directional search strategy allow the definition of solution approaches that turn out to be very effective in solving the problem under consideration. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.