Physical Sciences and Mathematics Commons^™

Parallel Algorithms For Multicriteria Shortest Path Problems, David L. Sonnier

Journal of the Arkansas Academy of Science

This paper presents two strategies for solving multicriteria shortest path problems with more than two criteria. Given an undirected graph within vertices, medges, and a set of K weights associated with each edge, we define a path as a sequence of edges from vertex s to vertex t. We want to find the Pareto-optimal set of paths from s to t. The solutions proposed herein are based on cluster computing using the Message-Passing Interface (MPI) extensions to the C programming language. We solve problems with 3 and 4 criteria, using up to 8 processors in parallel and using solutions based …