𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Shortest path algorithms using dynamic breadth-first search

✍ Scribed by Donald Goldfarb; Jianxiu Hao; Sheng-Roan Kai

Publisher
John Wiley and Sons
Year
1991
Tongue
English
Weight
1022 KB
Volume
21
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

A new O(nm) label-correcting algorithm is presented for finding shortest paths from a given node to all other nodes in a network of n nodes and m arcs or finding a directed cycle of negative length. In this algorithm, a node is scanned on the k-th scanning step only if its "label depth"-i.e., the length of the path corresponding to the distance label -equals k. Variants of this algorithm are discussed. and computational results show that several of these are very efficient. A new criterion for detecting a negative cycle that is also based on the label depth of a node is given. and Computational tests show that it is extremely effective.

πŸ“œ SIMILAR VOLUMES

Fully Dynamic Algorithms for Maintaining
Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
✍ Daniele Frigioni; Alberto Marchetti-Spaccamela; Umberto Nanni πŸ“‚ Article πŸ“… 2000 πŸ› Elsevier Science 🌐 English βš– 213 KB

We propose fully dynamic algorithms for maintaining the distances and the shortest paths from a single source in either a directed or an undirected graph with positive real edge weights, handling insertions, deletions, and weight updates of edges. The algorithms require linear space and optimal quer

Tracking Deformable Templates Using a Sh
Tracking Deformable Templates Using a Shortest Path Algorithm
✍ Marie-Pierre Dubuisson-Jolly; Alok Gupta πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 698 KB

This paper proposes a new technique to track deformable templates. We extend the typical graph algorithms that have been used for active contour recovery to incorporate shape information. The advantage of graph algorithms is that they are guaranteed to find the global minimum of the energy function.

New dynamic programming algorithms for t
New dynamic programming algorithms for the resource constrained elementary shortest path problem
✍ Giovanni Righini; Matteo Salani πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 173 KB

## Abstract The resource constrained elementary shortest path problem (RCESPP) arises as a pricing subproblem in branch‐and‐price algorithms for vehicle‐routing problems with additional constraints. We address the optimization of the RCESPP and we present and compare three methods. The first method