Search

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]

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]

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]