On an instance of the inverse shortest paths problem

The inverse shortest paths problem in a graph is considered, that is, the problem of recovering the arc costs given some information about the shortest paths in the graph. The problem is first motivated by some practical examples arising from applications. An algorithm based on the Goldfarb-Idnani method for convex quadratic programming is then proposed and analyzed for one of the instances of the problem. Preliminary numerical results are reported.     

A survey of geodesic paths on 3D surfaces

This survey gives a brief overview of theoretically and practically relevant algorithms to compute geodesic paths and distances on three-dimensional surfaces. The survey focuses on three-dimensional polyhedral surfaces. The goal of this survey is to identify the most relevant open problems, both theoretical and practical.     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

A fuzzy shortest path with the highest reliability

This paper concentrates on a shortest path problem on a network where arc lengths (costs) are not deterministic numbers, but imprecise ones. Here, costs of the shortest path problem are fuzzy intervals with increasing membership functions, whereas the membership function of the total cost of the shortest path is a fuzzy interval with a decreasing linear membership function. By the max–min criterion suggested in [R.E. Bellman, L.A. Zade, Decision-making in a fuzzy environment, Management Science 17B (1970) 141–164], the fuzzy shortest path problem can be treated as a mixed integer nonlinear programming problem. We show that this problem can be simplified into a bi-level programming problem that is very solvable. Here, we propose an efficient algorithm, based on the parametric shortest path problem for solving the bi-level programming problem. An illustrative example is given to demonstrate our proposed algorithm.     

Time version of the shortest path problem in a stochastic-flow network

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d$d$ units of data can be sent under the time constraint T$T$. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d,T)$(d,T)$-MPs and the system reliability can then be computed in terms of (d,T)$(d,T)$-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.     

Accelerated label setting algorithms for the elementary resource constrained shortest path problem

A label setting algorithm for solving the Elementary Resource Constrained Shortest Path Problem, using node resources to forbid repetition of nodes on the path, is implemented. A state-space augmenting approach for accelerating run times is considered. Several augmentation strategies are suggested and compared numerically.     

Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem

On a network with a cycle, where at least one cycle exists, the Floyd-Warshall algorithm is one of the algorithms most used for determining the least cost path between every pair of nodes. In this work a new algorithm for this problem is developed that requires less computational effort than the Floyd-Warshall algorithm. Furthermore, we show that the basis of our algorithm is much easier to understand, which might be an advantage for educational purposes. A small example validates our algorithm and shows its implementation.     

A note on weighted composition operators on the weighted Bergman space

This paper gives a note on weighted composition operators on the weighted Bergman space, which shows that for a fixed composition symbol, the weighted composition operators are bounded on the weighted Bergman space only with bounded weighted symbols if and only if the composition symbol is a finite Blaschke product.     

A comparison of heuristic best-first algorithms for bicriterion shortest path problems

A variety of algorithms have been proposed to solve the bicriterion shortest path problem. This article analyzes and compares the performance of three best-first (label-setting) algorithms that accept heuristic information to improve efficiency. These are NAMOA^∗, MOA^∗, and Tung & Chew’s algorithm (TC). A set of experiments explores the impact of heuristic information in search efficiency, and the relative performance of the algorithms. The analysis reveals that NAMOA^∗ is the best option for difficult problems. Its time performance can benefit considerably from heuristic information, though not in all cases. The performance of TC is similar but somewhat worse. However, the time performance of MOA^∗ is found to degrade considerably with the use of heuristic information in most cases. Explanations are provided for these phenomena.     

On the use of an inverse shortest paths algorithm for recovering linearly correlated costs

This paper considers the inverse shortest paths problem where arc costs are subject to correlation constraints. The motivation for this research arises from applications in traffic modelling and seismic tomography. A new method is proposed for solving this class of problems. It is constructed as a generalization of the algorithm presented in Burton and Toint (Mathematical Programming 53, 1992) for uncorrelated inverse shortest paths. Preliminary numerical experience with the new method is presented and discussed.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths

If each negative length arc of a digraphG is acyclic, i.e., does not belong to any cycle, then we show that the shortest paths from a given node to all other nodes can be computed inO(V ²) time, whereV is the number of nodes inG.     

A transformation of hard (equality constrained) knapsack problems into constrained shortest path problems

The purpose of this paper is to show how hard (equality constrained) knapsack problems may be converted into constrained shortest path problems. Several directions along which such a transformation might be exploited for algorithmic purposes are suggested.     

A short note on the weighted sub-partition mean of integers

In this note we study weighted sub-partitions (i₁,…,i_l) of positive integers on a number n with the greatest sub-partition mean , where is a weight function. We show that this problem is closely related with the problem of computing the eigenvalue of a Toeplitz matrix in a specific form.     

On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

A note on the separation of subtour elimination constraints in elementary shortest path problems

This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.     

Analysis of the asymmetric shortest queue problem

In this paper we study a system consisting of two parallel servers withdifferent service rates. Jobs arrive according to a Poisson stream and generate an exponentially distributed workload. On arrival a job joins the shortest queue and in case both queues have equal lengths, he joins the first queue with probabilityq and the second one with probability 1 −q, whereq is an arbitrary number between 0 and 1. In a previous paper we showed for the symmetric problem, that is for equal service rates andq = 1/2, that the equilibrium distribution of the lengths of the two queues can be exactly represented by an infinite sum of product form solutions by using an elementary compensation procedure. The main purpose of the present paper is to prove a similar product form result for the asymmetric problem by using a generalization of the compensation procedure. Furthermore, it is shown that the product form representation leads to a numerically efficient algorithm. Essentially, the method exploits the convergence properties of the series of product forms. Because of the fast convergence an efficient method is obtained with upper and lower bounds for the exact solution. For states further away from the origin the convergence is faster. This aspect is also exploited in the paper.