Improved Yen’s Algorithm for 2nd-Shortest Path Problem
Junlin Tian · International Journal of Computational and Experimental Science and Engineering · 2025
This paper introduces an algorithm designed to find the shortest and second shortest paths between two nodes in a network. Path optimization plays a crucial role in various fields, such as urban road management, network communication, and traffic planning. Numerous algorithms and insights inspired by machine learning have been developed, leading to valuable outcomes in these areas. However, many existing algorithms are mainly focused on minimizing path duration, and they often neglect other important factors such as cost, motor heating, and battery level, which can substantially affect the process. This study presents an enhancement to Yen’s algorithm with the A star algorithm, aiming not only to achieve a shorter time but also to reduce the associated costs. In many practical scenarios, algorithms that target the absolute shortest travel time often incur higher costs. Consequently, the second shortest path identified by Yen’s algorithm is valuable because it not only meets the requirement for a shorter travel time but also tends to incur lower costs compared to the shortest path. Then this work try to proof this model can be a reduction of Knapsack problem. This study uses the main roads in Lanzhou City as an example, using network topology to establish a coordinate system. By considering the time (t) and cost (c) associated with different transportation options, this study aims to develop a solution that more accurately reflects practical conditions and expected outcomes. The results indicate that the proposed algorithm is more effective at meeting the time and cost requirements compared to the original algorithm.