An Optimal Algorithm for Linear Fractional Shortest Path Problem

The shortest path problem is one of the most important issues among network problems. In this paper, an extension of this problem is considered wherein each arc possesses two parameters (such as cost and time). The object in this problem is to find a path between two specified nodes that minimizes cost per unit time. Since such an objective involves minimizing the fraction of two linear objectives, it is called a linear fractional shortest path problem (LFSP). An algorithm, the Modified Updated Objective Function Algorithm, is developed for this problem. This algorithm outperforms the Multi-Labeling Algorithm that was proposed by Roan and Roan, solves acyclic networks optimally. Computational results on the performance of these two algorithms are presented and compared.