A note on k‐shortest paths problem

It is well‐known that in a directed graph, if deleting any edge will not affect the shortest distance between two specific vertices s and t, then there are two edge‐disjoint paths from s to t and both of them are shortest paths. In this article, we generalize this to shortest k edge‐disjoint s‐t paths for any positive integer k. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 34‐37, 2011     

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.     

A note on the partitioning shortest path algorithm

Recently Glover, Klingman and Phillips proposed the Partitioning Shortest Path (PSP) algorithm. The PSP algorithm includes as variants most of the known algorithms for the shortest path problem. In a subsequent paper, together with Schneider, they proposed several variants of the PSP and conducted computational tests. Three of the variants were the first polynomially bounded shortest path algoriths to maintain sharp labels as defined by Shier and Witzgall. Two of these variants had computational complexity O(|N|²|A|), the other O(|N|³). In this note, we add a new step to the PSP algorithm resulting in new variants also scanning from sharp labels and having computational complexity O(|N|³) for two of them and O(|N|²) for the other. This new step also provides a test for the early detection of negative length cycles.     

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.     

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.     

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 shortest cycle covers of cubic graphs

Let SCC₃(G) be the length of a shortest 3‐cycle cover of a bridgeless cubic graph G. It is proved in this note that if G contains no circuit of length 5 (an improvement of Jackson's (JCTB 1994) result: if G has girth at least 7) and if all 5‐circuits of G are disjoint (a new upper bound of SCC₃(G) for the special class of graphs).     

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.     

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.     

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 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 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.     

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.