Search

The shortest path problem is a classic optimization problem in graph theory and computer technology. It involves identifying the shortest path between two nodes in a graph, where each edge has a numerical weight. In this paper, we put our effort into examining the use of the dynamic programming method to evaluate the shortest path (SP) between the two specified nodes in a multistage network where the parameter is a multi-value neutrosophic number (MVNN). Firstly, we propose an algorithm based on the forward and backward approach in an uncertain environment and also implement our approach in the Python-3 programming language. Furthermore, a numerical illustration has been provided to showcase the effectiveness and robustness of the novel model. [ABSTRACT FROM AUTHOR]

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]

The shortest path (SP) problem (SPP) has several applications in graph theory. It can be used to calculate the distance between the provided initial and final vertex in a network. In this paper, we employed the Fermatean neutrosophic number as the appropriate edge weight of the network to estimate the SP connecting the start and end vertex. This technique is highly useful in establishing the shortest path for the decision-maker under uncertainty. We also investigated its effectiveness in comparison to several existing methods. Finally, a few numerical tests were performed to demonstrate the validity and stability of this new technique, as well as to compare different types of shortest paths with different networks. [ABSTRACT FROM AUTHOR]

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]

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]

Shortest path (SP) problem is a classical combinatorial optimization problem, which has various application domains such as communication network routing and location-based services under cloud environment. However, maze-type networks, sparse networks with many pairs of disconnected nodes, had rarely been studied. A maze-type network is more difficult to analyze than common dense network, since it has rare feasible paths. Moreover, precedence constraints among the nodes further increase the complexity of maze-type network, and this paper aims to develop genetic algorithms for finding the shortest path in maze-type network with precedence constraints. In order to address precedence constrained maze-type shortest path (PCM-SP) problem, the fitness switching genetic algorithm (FSWGA), which has been developed to solve the unconstrained maze-type shortest path (M-SP) problems, is revised by adopting position listing representation as encoding scheme and applying two enhanced decoding procedures. In addition, genetic operator of candidate order based genetic algorithm (COGA) is used to explore the search space effectively, and experiment results demonstrate that the enhanced FSWGA can solve PCM-SP problems more effectively than the previous FSWGA. [ABSTRACT FROM AUTHOR]

To find the shortest path between the nodes of a graph, different algorithms like Bellman-Ford, Dijkstra, Floyd-Warshall and Johnson exist. However, in this paper, the issue of shortest path problem with special reference to Dijkstra's algorithm is presented. An idea of shortlisting the appropriate nodes in a graph is proposed and presented, which is then used to find the shortest path with the help of Dijkstra's algorithm. This complete work - named Capton algorithm-provides a solution to single source shortest path problem with minimized time complexity as compared to Dijkstra's algorithm. [ABSTRACT FROM AUTHOR]

Copyright of Military Engineer / Hadmérnök is the property of National University of Public Service and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract: We study new decision and optimization problems of finding a simple path between two given vertices in an arc weighted directed multigraph such that the path length is equal to a given number or it does not fall into the given forbidden intervals (gaps). A fairly complete computational complexity classification is provided and exact and approximation algorithms are suggested. [ABSTRACT FROM AUTHOR]

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]

Copyright of Military Engineer / Hadmérnök is the property of National University of Public Service and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

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]

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]

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]

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]

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]

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]

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]

This paper presents an extensive analysis of a sample of a social network of musicians. The network sample is first analyzed using standard complex network techniques to verify that it has similar properties to other web-derived complex networks. Content-based pairwise dissimilarity values between the musical data associated with the network sample are computed, and the relationship between those content-based distances and distances from network theory explored. Following this exploration, hybrid graphs and distance measures are constructed, and used to examine the community structure of the artist network. Finally, results of these investigations are shown to be mostly orthogonal between these distance spaces. These results are considered with a focus recommendation and discovery applications employing these hybrid measures as their basis. [ABSTRACT FROM PUBLISHER]

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]

Abstract: In this paper, we propose an efficient method for implementing Dijkstra''s algorithm for the Single Source Shortest Path Problem (SSSPP) in a graph whose edges have positive length, and where there are few distinct edge lengths. The SSSPP is one of the most widely studied problems in theoretical computer science and operations research. On a graph with n vertices, m edges and K distinct edge lengths, our algorithm runs in time if , and time, otherwise. We tested our algorithm against some of the fastest algorithms for SSSPP on graphs with arbitrary but positive lengths. Our experiments on graphs with few edge lengths confirmed our theoretical results, as the proposed algorithm consistently dominated the other SSSPP algorithms, which did not exploit the special structure of having few distinct edge lengths. [Copyright &y& Elsevier]

The representation of a genome by oligonucleotide probes is a prerequisite for the analysis of many of its basic properties, such as transcription factor binding sites, chromosomal breakpoints, gene expression of known genes and detection of novel genes, in particular those coding for small RNAs. An ideal representation would consist of a high density set of oligonucleotides with similar melting temperatures that do not cross-hybridize with other regions of the genome and are equidistantly spaced. The implementation of such design is typically called a tiling array or genome array. We formulate the minimal cost tiling path problem for the selection of oligonucleotides from a set of candidates. Computing the selection of probes requires multi-criterion optimization, which we cast into a shortest path problem. Standard algorithms running in linear time allow us to compute globally optimal tiling paths from millions of candidate oligonucleotides on a standard desktop computer for most problem variants. The solutions to this multi-criterion optimization are spatially adaptive to the problem instance. Our formulation incorporates experimental constraints with respect to specific regions of interest and trade offs between hybridization parameters, probe quality and tiling density easily. [ABSTRACT FROM PUBLISHER]