In this paper we describe an exact algorithm that constructs all Pareto optimal solutions of the biobjective minimum risk minimum length spanning trees problem.The method constructs directly the Pareto optimal spanning trees without constructing the entire classes of optimal spanning trees with respect to the length and with respect to the risk criterion.We formulate the theorems that prove the correctness and computational complexity of the proposed algorithms.Also, we illustrate the method using a comprehensive numerical example.The computational complexity of the algorithm that constructs the complete Pareto front of the problem is O(s(m + n lg n)), where s is a constant that depends on the number of all Pareto optimal solutions and a predefined constant that can be used to limit the number of constructed solutions.

We propose an exact method that finds the complete Pareto front of the biobjective minimum length minimum risk spanning trees problem.The proposed method consists of the solution of two problems.The first problem is to compute a list of all minimum spanning trees with respect of the length criterion.The second problem is to construct the complete Pareto front itself, based on the list of all minimum spanning trees, found using the solution of the first problem.We prove mathematically the correctness of all proposed algorithms, and we discuss their computational complexity.We also illustrate the presented solution with detailed numerical examples.

Many applications in practice involve the search for a shortest path in a network by optimizing two conflicting objective functions.Such problems often are referred to as biobjective optimization problems.Their goal is to find special optimal paths that are nondominated and are also known in the specialized literature as to as Pareto optimal.While most of the existing methods aim to find the minimum complete set of Pareto optimal paths, we propose an approach that is able to generate a list of all Pareto optimal solutions in a given network.The described method solves the biobjective optimization problem in the case in which the first objective function is a linear (MINSUM), while the second objective function is from the "bottleneck" type (MAXMIN).The presented approach is based on two modifications of the Dijkstra's shortest path algorithm that solve the MINSUM and the MAXMIN problems respectively.We prove the correctness and the computational complexity of the presented algorithms.Also, we provide detailed numerical examples that illustrate their execution.