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

Adrien Durand (), Timothé Watteau, Georges Ghazi () and Ruxandra Mihaela Botez ()
Additional contact information
Adrien Durand: Laboratory of Applied Research in Active Control, Avionics and AeroServoElasticity (LARCASE), École de Technologie Supérieure (ÉTS), Université de Québec, Montréal, QC H3C 1K3, Canada
Timothé Watteau: Laboratory of Applied Research in Active Control, Avionics and AeroServoElasticity (LARCASE), École de Technologie Supérieure (ÉTS), Université de Québec, Montréal, QC H3C 1K3, Canada
Georges Ghazi: Laboratory of Applied Research in Active Control, Avionics and AeroServoElasticity (LARCASE), École de Technologie Supérieure (ÉTS), Université de Québec, Montréal, QC H3C 1K3, Canada
Ruxandra Mihaela Botez: Laboratory of Applied Research in Active Control, Avionics and AeroServoElasticity (LARCASE), École de Technologie Supérieure (ÉTS), Université de Québec, Montréal, QC H3C 1K3, Canada

Mathematics, 2024, vol. 12, issue 19, 1-24

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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/19/2995/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/19/2995/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:19:p:2995-:d:1486144

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().