- 期刊
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.
延伸閱讀
- Roan, J. (2003). Algorithms for Linear Fractional Shortest Path Problem with Time Windows. Pan-Pacific Management Review, 6(1), 75-83. https://doi.org/10.30166/PPMR.200301.0004
- Biswas, S. S., Alam, B., & Doja, M. N. (2013). An Algorithm for Extracting Intuitionistic Fuzzy Shortest Path in a Graph. Applied Computational Intelligence and Soft Computing, 2013(), 163-167. https://doi.org/10.1155/2013/970197
- Yu, C. Y. (2002). An efficient fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system [master's thesis, Yuan Ze University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0009-0112200611345617
- Hsieh, Y. H. (2007). Optimal Algorithms for the Interval Location Problem with Range Constraints on Length and Average [doctoral dissertation, National Tsing Hua University]. Airiti Library. https://www.airitilibrary.com/Article/Detail?DocID=U0016-1411200715141517
- 謝逢鳴（2006）。Research on the Shortest Path Algorithm with Pre-processing〔碩士論文，淡江大學〕。華藝線上圖書館。https://doi.org/10.6846/TKU.2006.00272