Durand, Adrien, Watteau, Timothé, Ghazi, Georges and Botez, Ruxandra Mihaela.
2024.
« Generalized shortest path problem: An innovative approach for non-additive problems in conditional weighted graphs ».
Mathematics, vol. 12, nº 19.
Compte des citations dans Scopus : 1.
Preview |
PDF
Ghazi-G-2024-29780.pdf - Published Version Use licence: Creative Commons CC BY. Download (2MB) | Preview |
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
| Item Type: | Peer reviewed article published in a journal |
|---|---|
| Professor: | Professor Ghazi, Georges Botez, Ruxandra |
| Affiliation: | Génie des systèmes, Génie des systèmes |
| Date Deposited: | 05 Nov 2024 19:39 |
| Last Modified: | 07 Nov 2024 20:21 |
| URI: | https://espace2.etsmtl.ca/id/eprint/29780 |
Actions (login required)
 |
View Item |