Generalized Shortest Path Problem: An Innovative Approach for Non-Additive Problems in Conditional Weighted Graphs

Abstract

The shortest path problem is fundamental in graph theory and has been studied extensively due to its practical importance. Despite this aspect, finding the shortest path between two nodes remains a significant challenge in many applications, as it often becomes complex and time consuming. This complexity becomes even more challenging when constraints make the problem non-additive, thereby increasing the difficulty of finding the optimal path. The objective of this paper is to present a broad perspective on the conventional shortest path problem. It introduces a new method to classify cost functions associated with graphs by defining distinct sets of cost functions. This classification facilitates the exploration of line graphs and an understanding of the upper bounds on the transformation sizes for these types of graphs. Based on these foundations, the paper proposes a practical methodology for solving non-additive shortest path problems. It also provides a proof of optimality and establishes an upper bound on the algorithmic cost of the proposed methodology. This study not only expands the scope of traditional shortest path problems but also highlights their computational complexity and potential solutions.

Keywords

• universal shortest path problem
• line graphs
• graph cost functions
• optimization techniques