| Abstract: | 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 |
