The Labelling Algorithm for the Multiobjective Shortest Path Problem

: In this paper we analyse the labelling algorithm for the multiobjective shortest path problem considering this problem as a generalization of the classical shortest path problem. In opposition to what is generally considered, no assumption is made that leads to some loss of generality which implies the generalization of some concepts such as finiteness and boundness -- which are fundamental in the general optimal path problems. The optimality principles, the support of any form of the labelling algorithm, are also generalized. The special acyclic network case is considered yet and its set of optimal paths is determined with a single scan in the set of arcs. The complexity analysis of the labelling algorithm for the multiobjective shortest path problem is examined too. Keywords: optimal path, multiobjective shortest path, dominance relation, complexity analysis. 1 Introduction The shortest path problem is a classical network optimization problem which has merit special ..