𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Dual algorithms for the shortest path tree problem

✍ Scribed by Pallottino, Stefano; Scutell�, Maria Grazia

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
117 KB
Volume
29
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, ''local'' and ''global'' dual updating operations are performed at the nodes in order to enlarge a partial shortest path tree, which at the beginning contains only the root node, until a shortest path tree is found. Several kinds of dual updating operations are proposed, which allow one to derive different dual algorithms from a general schema. One of them, in particular, which is based only on global operations, can be viewed as a dual interpretation of Dijkstra's classical algorithm. Due to their structure, all the proposed algorithms are suitable for parallel implementation. They are also suitable for reoptimization approaches, when the computation of shortest paths from different root nodes is required.

📜 SIMILAR VOLUMES

A tabu search algorithm for the Capacita
A tabu search algorithm for the Capacitated Shortest Spanning Tree Problem
✍ Sharaiha, Yazid M.; Gendreau, Michel; Laporte, Gilbert; Osman, Ibrahim H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 2 views

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynami

Iterative methods for dynamic stochastic
Iterative methods for dynamic stochastic shortest path problems
✍ Raymond K. Cheung 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

We consider a routing policy that forms a dynamic shortest path in a network with independent, positive and discrete random arc costs. When visiting a node in the network, the costs for the arcs going out of this node are realized, and then the policy will determine which node to visit next with the

The time-dependent shortest pair of disj
The time-dependent shortest pair of disjoint paths problem: Complexity, models, and algorithms
✍ Sherali, Hanif D.; Ozbay, Kaan; Subramanian, Shivaram 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB 👁 1 views

In this paper, we examine complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. Such disjoint paths address the issu

State space partitioning methods for sto
State space partitioning methods for stochastic shortest path problems
✍ Alexopoulos, Christos 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

This paper describes methods for computing measures related to shortest paths in networks with discrete random arc lengths. These measures include the probability that there exists a path with length not exceeding a specified value and the probability that a given path is shortest. The proposed meth

A simpleO(n2) algorithm for the all-pair
A simpleO(n2) algorithm for the all-pairs shortest path problem on an interval graph
✍ Mirchandani, Prakash 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 288 KB 👁 1 views

Let G denote an interval graph with n vertices and unit weight edges. In this paper, we present a simple O(n') algorithm for solving the all-pairs shortest path problem on graph G . A recent algorithm for this problem has the same time-complexity but is fairly complicated to describe. However, our a

A dynamic programming algorithm for the
A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
✍ Ioachim, Irina; G�linas, Sylvie; Soumis, Fran�ois; Desrosiers, Jacques 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 154 KB 👁 1 views

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem, we propose a new dynamic programming algorithm w