Durand, Adrien, Watteau, Timothé, Ghazi, Georges et Botez, Ruxandra Mihaela.
2024.
« Generalized shortest path problem: An innovative approach for non-additive problems in conditional weighted graphs ».
Mathematics, vol. 12, nº 19.
Prévisualisation |
PDF
Ghazi-G-2024-29780.pdf - Version publiée Licence d'utilisation : Creative Commons CC BY. Télécharger (2MB) | Prévisualisation |
Résumé
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
| Type de document: | Article publié dans une revue, révisé par les pairs |
|---|---|
| Professeur: | Professeur Ghazi, Georges Botez, Ruxandra |
| Affiliation: | Génie des systèmes, Génie des systèmes |
| Date de dépôt: | 05 nov. 2024 19:39 |
| Dernière modification: | 07 nov. 2024 20:21 |
| URI: | https://espace2.etsmtl.ca/id/eprint/29780 |
Actions (Authentification requise)
 |
Dernière vérification avant le dépôt |