An O(n2) shortest path algorithm for a non-rotating convex body

We investigate the problem of moving a convex body in the plane from one location to another while avoiding a given collection of polygonal obstacles. The method we propose is applicable when the convex body is not allowed to rotate. If n denotes the total size of all polygonal obstacles, the method yields an O(n²) algorithm for finding a shortest path from the initial to the final location. In solving this problem, we develop some new tools in computational geometry that may be of independent interest.     

An efficient algorithm for perturbed shortest path problems

We present an efficient algorithm for perturbed shortest paths problems that arise, e.g., in dynamic games. Via a minmax version of Dijkstra's algorithm we compute piecewise constant upper and lower bounds on the upper value function of the game. Convergence of the bounds in the limit of vanishing cell diameter can be proved. The method is numerically demonstrated on a simple 2d dynamic game, the homicidal chauffeur. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

An efficient label setting/correcting shortest path algorithm

We design a new label shortest path algorithm by applying the concept of a pseudo permanent label. This approach allows an algorithm to partition the set of nodes into two new sets: pseudo permanently labeled nodes and its complementary set. From this point of view, this new label method can be considered as a label setting method. Moreover, at least one node becomes permanently labeled when some nodes which belong to the set of pseudo permanently labeled nodes are scanned in each iteration of the algorithm. In the case of networks with non-negative length arcs it is easy to prove that this node has the minimum distance label among the non-pseudo permanently labeled nodes. On the other hand, it is not known during the computation which pseudo permanently labeled nodes are permanently labeled. Therefore, all distance labels are temporary and the algorithm becomes a label correcting method. Nevertheless, the proposed algorithm exhibits some nice features, such as: (1) the time bound for the running of the algorithm for a network with n nodes and m arcs is O(nm); (2) the number of node scan operations in the algorithm is less than the number of these operations in the previous label correcting algorithms as is observed in the computational experience; (3) the algorithm incorporates two new rules which allow easy detection of a negative cycle in the network; (4) the algorithm is quite simple and very easy to implement, and does not require sophisticated data structures; (5) the algorithm exhibits flexibility in the order in which the new pseudo permanently labeled nodes are scanned. The above features are possible through the application of the pseudo permanent label concept.     

A bicriterion shortest path algorithm

Among the network models, one of the more popular is the so called shortest path problem. This model is used whenever it is intended to minimize a linear function which represents a distance between a predetermined pair of nodes in a given network.Often a single objective function is not sufficient to completely characterize some real-world problems. For instance, in a road network two parameters - as cost and time - can be assigned to each arc. Clearly the fastest path may be too costly. Nevertheless the decision-maker must choose one solution, possibly not the best for both criteria.In this paper we present an algorithm for this problem. With this algorithm a special set of paths (the set of Pareto optimal paths) is determined. One objective for any Pareto optimal path can not be improved without worsening the other one.     

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.     

Improvements for the Thresh X2 shortest path algorithm

The Thresh X2 algorithm has been shown to dominate other shortest path algorithms over a wide variety of conditions. When used on random networks which have exponentially or normally distributed edge weights the performance of X2 degrades. We develop techniques which improve X2's performance up to 33% in these cases.     

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(δ ² n), where δ is the maximum node degree in communication graph.     

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.     

An applicable method for solving the shortest path problems

A theorem of Hardy, Littlewood, and Polya, first time is used to find the variational form of the well known shortest path problem, and as a consequence of that theorem, one can find the shortest path problem via quadratic programming. In this paper, we use measure theory to solve this problem. The shortest path problem can be written as an optimal control problem. Then the resulting distributed control problem is expressed in measure theoretical form, in fact an infinite dimensional linear programming problem. The optimal measure representing the shortest path problem is approximated by the solution of a finite dimensional linear programming problem.     

An origin-based model for unique shortest path routing

Link weights are the main parameters of shortest path routing protocols, the most commonly used protocols for IP networks. The problem of optimally setting link weights for unique shortest path routing is addressed. Due to the complexity of the constraints involved, there exist challenges to formulate the problem in such a way based on which a more efficient solution algorithm than the existing ones may be developed. In this paper, an exact formulation is first introduced and then mathematically proved correct. It is further illustrated that the formulation has advantages over a prior one in terms of both constraint structure and model size for a proposed decomposition method to solve the problem.     

A path following algorithm for a class of convex programming problems

We present a primal-dual path following interior algorithm for a class of linearly constrained convex programming problems with non-negative decision variables. We introduce the definition of a Scaled Lipschitz Condition and show that if the objective function satisfies the Scaled Lipschitz Condition then, at each iteration, our algorithm reduces the duality gap by at least a factor of (1–/n), where is positive and depends on the curvature of the objective function, by means of solving a system of linear equations which requires no more than O(n³) arithmetic operations. The class of functions having the Scaled Lipschitz Condition includes linear, convex quadratic and entropy functions.     

Martins' algorithm revisited for multi-objective shortest path problems with a MaxMin cost function

This paper presents a direct extension of the label setting algorithm proposed by Martins in 1984 for the shortest path problem with multiple objectives. This extended version computes all the efficient paths from a given source vertex, to all the other vertices of the network. The algorithm copes with problems in which the "cost values" associated with the network arcs are positive. The proposed extension can handle objective functions that are either of the "sum" type or of the "bottleneck" type. The main modifications to Martins' algorithm for multi-objective shortest path problems are linked to the dominance test and the procedure for identifying efficient paths. The algorithmic features are described and a didactic example is provided to illustrate the working principle. The results of numerical experiments concerning the number of efficient solutions produced and the CPU time consumed for several configurations of objectives, on a set of randomly generated networks, are also provided. Received: February 2005 / Revised version: June 2005 AMS classification: 90C29, 90C27, 05C38, 90B18, 68M12     

An aggregate label setting policy for the multi-objective shortest path problem

We consider label setting algorithms for the multi-objective shortest path problem with any number of sum and bottleneck objectives. We propose a weighted sum aggregate ordering of the labels, specifically tailored to combine sum and bottleneck objectives. We show that the aggregate order leads to a consistent reduction of solution times (up to two-thirds) with respect to the classical lexicographic order.     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

An extension of labeling techniques for finding shortest path trees

Label setting techniques are all based on Dijkstra’s condition of always scanning the node with the minimum label, which guarantees that each node will be scanned exactly once; while this condition is sufficient it is not necessary. In this paper, we discuss less restrictive conditions that allow the scanning of a node that does not have the minimum label, yet still maintaining sufficiency in scanning each node exactly once; various potential shortest path schemes are discussed, based on these conditions. Two approaches, a label setting and a flexible hybrid one are designed and implemented. The performance of the algorithms is assessed both theoretically and computationally. For comparative analysis purposes, three additional shortest path algorithms – the commonly cited in the literature – are coded and tested. The results indicate that the approaches that rely on the less restrictive optimality conditions perform substantially better for a wide range of network topologies.     

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.